Lintcode 1390. Short Encoding of Words

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a "#" character.

What is the length of the shortest reference string S possible that encodes the given words?

Example

**Input**: words = ["time", "me", "bell"]
**Output**: 10
**Explanation**: S = "time#bell#" and indexes = [0, 2, 5].

Notice

• 1 <= words.length <= 2000.
• 1 <= words[i].length <= 7.
• Each word has only lowercase letters.

Solution:

Two words can be compressed if and only if they share the same suffix. For e.g. time, me, ime can be compressed. But time and im cannot be compressed. And time and ame cannot be compressed as well.

So the solution is to use a trie to store all the words in reverse order. In the end, count the number of nodes of the trie and calculate the final length. 

Code (Java):

public class Solution {
    /**
     * @param words: 
     * @return: nothing
     */
    public int minimumLengthEncoding(String[] words) {
        // 
        if (words == null || words.length == 0) {
            return 0;
        }
        
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        
        return trie.getLength();
    }
}

class TrieNode {
    public TrieNode[] children;
    
    public TrieNode() {
        this.children = new TrieNode[26];
    }
}

class Trie {
    private TrieNode root;
    
    public Trie() {
        this.root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode p = root;
        
        for (int i = word.length() - 1; i >= 0; i--) {
            char c = word.charAt(i);
            if (p.children[c - 'a'] == null) {
                p.children[c - 'a'] = new TrieNode();
            }
            
            p = p.children[c - 'a'];
        }
    }
    
    public int getLength() {
        TrieNode p = root;
        
        return dfs(p, 0);
    }
    
    private int dfs(TrieNode p, int depth) {
        // if p is a leaf node, get the number and return
        boolean leaf = true;
        
        int len = 0;
        
        for (int i = 0; i < 26; i++) {
            if (p.children[i] != null) {
                leaf = false;
                len += dfs(p.children[i], depth + 1);
            }
        }
        
        if (leaf) {
            len += depth + 1;
        }
        
        return len;
    }
    
}