A valid encoding of an array of words is any reference string s and array of indices indices such that:


	words.length == indices.length
	The reference string s ends with the '#' character.
	For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i].


Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.

&nbsp;
Example 1:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"


Example 2:

Input: words = ["t"]
Output: 2
Explanation: A valid encoding would be s = "t#" and indices = [0].


&nbsp;
Constraints:


	1 &lt;= words.length &lt;= 2000
	1 &lt;= words[i].length &lt;= 7
	words[i] consists of only lowercase letters.


class Solution:
    def minimumLengthEncoding(self, words):
        
        
        # root of suffix trie
        trie_root = dict()
        
        # helper function to judge leaf node
        isLeafNode = lambda node: len(node) == 0
        
        # collection of tail nodes
        tail_nodes = []
        
        # set of unique words
        unique_words = set(words)
        
        # scan each word
        for word in unique_words:
            
            # build suffix trie from root node
            cur = trie_root
            
            # scan each character in reversed order
            for char in reversed(word):
                
                # update trie
                cur[char] = cur.get(char, dict() )
                
                # go to next level
                cur = cur[char]
            
            # save tail nodes with corresponding word length, +1 is for '#' symbol
            tail_nodes.append( (cur, len(word)+1) )

        # summation of the length with all tail node which is also a leaf node
        return sum( suffix_length for node, suffix_length in tail_nodes if isLeafNode(node) )
class Node {
    private boolean flag;
    private Node[] children;

    public Node () {
        flag = false;
        children = new Node[26];
        Arrays.fill (children, null);
    }

    public boolean getFlag () {
        return flag;
    }

    public Node getChild (int index) {
        return children[index];
    }

    public boolean hasChild (int index) {
        return children[index] != null;
    }

    public void setFlag (boolean flag) {
        this.flag = flag;
    }

    public void makeChild (int index) {
        children[index] = new Node();
    }
}

class Trie {
    private Node root;

    public Trie () {
        root = new Node();
    }

    public int addWord (String word) {

        boolean flag = true;
        Node node = root;
        int count = 0;

        for (int i = word.length () - 1; i >= 0; --i) {
            int index = (int) word.charAt(i) - 97;

            if (!node.hasChild (index)) {
                flag = false;
                node.makeChild (index);
            }

            node = node.getChild (index);
            if (node.getFlag()) {
                node.setFlag (false);
                count -= word.length() - i + 1;

                if (i == 0)
                    flag = false;
            }
        }

        if (!flag)
            node.setFlag (true);

        return flag? count: count + 1 + word.length();
    }
}

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Trie trie = new Trie ();
        int size = 0;

        for (String word: words) {
            size += trie.addWord (word);
        }

        return size;
    }
}
class TrieNode{
public:
    bool isEnd;
    vector<TrieNode*> children;
    TrieNode(){
        isEnd = false;
        children = vector<TrieNode*>(26, NULL);
    }
};

class Trie{
public:
    TrieNode* root;
    Trie(){
        root = new TrieNode();
    }
    
    void insert(string& word, bool& isSuffix){
        auto cur = root;
        for(int i=0; i<word.size(); i++){
            int index = word[i] - 'a';
			
			//If new node is needed to be inserted for this word, then this word can't be suffix of some other word.
            if(cur->children[index] == NULL){
                isSuffix = false;
                cur->children[index] = new TrieNode();
            }
            cur = cur->children[index];
        }
        cur -> isEnd= true;
    }
};

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        sort(words.begin(), words.end(), [](string& a, string& b){
            return a.size() > b.size();
        });
        
        int res = 0;
        Trie* trie = new Trie();

		for(auto word: words){
            reverse(word.begin(), word.end());
            bool wordIsSuffix = true;
            trie->insert(word, wordIsSuffix);
            // If word is not suffix of some other word, it needs to be added separately
            if(!wordIsSuffix) res += word.size()+1; //+1 for '#'
        }
        return res;
    }
};
/**
 * @param {string[]} words
 * @return {number}
 */
class Trie {
    constructor(letter) {
        this.letter = letter;
        this.children = new Map();
        this.isWord = false;
    }
}

var minimumLengthEncoding = function(words) {
    let minEncodingLength = 0;
    const sortedWords = words.sort((a, b) => a.length - b.length);

    const buildTrie = (root, word, index) => {
        // This means we reached to the end of word, so mark it as a word and compute encoding length
        if (index < 0) {
            minEncodingLength += word.length + 1;
            root.isWord = true;
            return;
        }

        const character = word[index];
        // If we do not have a char in children, create a node and add it under root
        if (!root.children.has(character)) {
            const node = new Trie(character);
            root.children.set(character, node);
            buildTrie(node, word, index - 1);
            return;
        }

        const node = root.children.get(character);
        // Remove the common suffix length considered before since it would be covered as a part of current word traversal
        if (node.isWord) {
            node.isWord = false;
            minEncodingLength -= word.length - index + 1;
        }

        buildTrie(node, word, index - 1);
    };

    const root = new Trie();
    for (const word of sortedWords) {
        buildTrie(root, word, word.length - 1);
    }

    return minEncodingLength;
};
Short Encoding of Words