820. Short Encoding of Words

Question

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.

Solution 1

LeetCode这几天的每日一题时不让我学会字典树势不罢休啊……

字典树，参数isLeaf记录每个TireNode节点是否为叶子节点。
将单词倒序组建字典树，并维护isLeaf的属性。

计算从根节点到达每个叶子节点的长度再加一的和即可。

Code

class Solution {
    class TrieNode{
        TrieNode[] next = new TrieNode[26];
        boolean isLeaf;
    }
    TrieNode root;
    int count;
    
    public int minimumLengthEncoding(String[] words) {        
        count = 0;
        root = new TrieNode();
        
        for(String word : words){
            add(word);
        }
        countLeaves(root, 0);
        return count;
    }
    
    private void add(String word){
        TrieNode curr = root;
        for(int i = word.length()-1; i >= 0; i--){
            int index = word.charAt(i) - 'a';
            if(curr.next[index] == null){
                curr.isLeaf = false;
                curr.next[index] = new TrieNode();
                curr.next[index].isLeaf = true;
            }
            curr = curr.next[index];
        }
    }
    
    private void countLeaves(TrieNode root, int length){
        if(root.isLeaf){
            count += length + 1;
        } 
        else{
            for(int i = 0; i < 26; i++){
                if(root.next[i] != null) countLeaves(root.next[i], length+1);
            }
        }
    }
}

Solution 2

排序，将数组words根据单词倒序排序。
倒序构成字典树，如果展开新的字典树分支（创建新的TrieNode节点）则将count加入根节点到新节点的距离。

Code

class Solution {
    class TrieNode{
        TrieNode[] next = new TrieNode[26];
        boolean end;
    }
    TrieNode root;
    int count;
    
    public int minimumLengthEncoding(String[] words) {
        Arrays.sort(words, new Comparator<String>(){
            public int compare(String a, String b){
                int i = a.length()-1, j = b.length()-1;
                while(i >= 0 && j >= 0){
                    int index = a.charAt(i) - b.charAt(j);
                    if(index == 0){
                        i--;
                        j--;
                    }
                    else{
                        return index;
                    }
                }
                return j - i;
            }
        });
        
        count = 0;
        root = new TrieNode();
        
        for(String word : words){
            add(word);
        }
        
        return count;
    }
    
    private void add(String word){
        TrieNode curr = root;
        int length = 1;
        boolean newTrieNode = false;
        for(int i = word.length()-1; i >= 0; i--){
            int index = word.charAt(i) - 'a';
            if(curr.next[index] == null){
                curr.next[index] = new TrieNode();
                newTrieNode = true;
            }
            curr = curr.next[index];
            length++;
        }
        curr.end = true;
        if(newTrieNode) count += length;
    }
}

Solution 3

倒序重组字符串并记录到reversedWords[]数组，然后根据字典顺序排序。
如果数组的上一个字符串不是下一个字符串的前缀，则加入上一个字符串的长度加一。

Code

class Solution {    
    public int minimumLengthEncoding(String[] words) {
        String[] reversedWords = new String[words.length];
        int count = 0, index = 0;
        for(String word : words){
            reversedWords[index] = new StringBuffer(word).reverse().toString();
            index++;
        }
        
        Arrays.sort(reversedWords);
        for(int i = 0; i < words.length-1; i++){
            if(!reversedWords[i+1].startsWith(reversedWords[i])) count += reversedWords[i].length()+1;
        }
        count += reversedWords[words.length-1].length()+1;
        return count;
    }
}