LeetCode——单词的压缩编码

NO.820 单词的压缩编码中等

如果不了解什么是前缀树，可以先去做一下NO.208 实现Trie(前缀树)了解一下这种数据结构。

如果需要大量的找前缀或者找后缀，一般都可以使用字典树去进行搜索。

思路一：字典树 字典树又名前缀树、Trie树。

本题的难点在于如何判断一个单词是否为另一个单词的后缀。

等等！明明前面再说前缀前缀怎么突然变成后缀了？

道理是一样的，只需要将每个单词都翻转一下或者逆序插入前缀树，就后缀问题换成了前缀的问题。

有一点需要注意：必须是先插长单词，再插短单词。否则例如先插入了”em”、再插入”emit”依然会都插入成功，如果先插入”emit”再插入”em”则会忽略”em”。所以我们需要对words数组依据单词长度排序。

public int minimumLengthEncoding(String[] words) {
    int len=0;
    Trie trie=new Trie();
    //按照单词从长到短排序
    Arrays.sort(words,(e1,e2)->e2.length()-e1.length());
    //单词依次向字典树进行插入，记录新增单词的长度
    for (String word : words) {
        len+=trie.insertWord(word);
    }
    return len;
}

//定义一个TrieTree
class Trie{
    private Trie[] next;
    private final int SIZE=26;

    Trie(){
        this.next=new Trie[SIZE];
    }

    public int insertWord(String word){
        boolean isNew=false;//是否为新单词
        Trie curr = this;
        for (int i = word.length()-1; i >= 0; i--) {
            char c = word.charAt(i);
            if (curr.next[c - 'a'] == null) {
                isNew=true;
                curr.next[c - 'a']=new Trie();
            }
            curr=curr.next[c - 'a'];
        }
        //如果是新单词就返回单词长度+'#'，否则是旧单词的前缀返回0
        return isNew?word.length()+1:0;
    }
}

时间复杂度：O(∑words[i].length) 所有单词的字符数量和。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.820 单词的压缩编码 中等

NO.820 单词的压缩编码中等