单词的压缩编码

题目

给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。

例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。

对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。

那么成功对给定单词列表进行编码的最小字符串长度是多少呢？

示例：

输入: words = ["time", "me", "bell"]
输出: 10
说明: S = "time#bell#" ， indexes = [0, 2, 5] 。

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 7
每个单词都是小写字母 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/short-encoding-of-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

如果有了解过分词或者字典树的朋友一看就知道可以使用字典树来解决.

而不知道的最简单最容易想到的肯定还是暴力法.我的暴力法是将最大字符串找出然后和后面的去比.同时将最大的和后面符合可以合并逻辑的字符串都置为空字符串.理所当然的,效率很低......

那么改进的暴力法可以将所有字符串翻转,然后将字符串根据字典排序,此时只要比较前缀即可.

代码

最初版暴力法

class Solution {
    public int minimumLengthEncoding(String[] words) {
        //情况特判
        if(words.length == 0){
            return 0;
        }
        StringBuilder sb = new StringBuilder();
        //需要先找到最大长度的字符串,先将其添加进入.然后判断他的符合条件,再加入次一级的字符串.
        int indexMax = 0;
        int num = words.length;
        boolean flag = true;
        while(num > 0){
            for(int i = 0;i < words.length;i++){
                if(words[i].length() != 0){
                    flag = false;
                }
                if(words[indexMax].length() < words[i].length()){
                    indexMax = i;
                }
            }
            if (flag){
                break;
            }
            String maxValue = words[indexMax];
            if(maxValue.length() != 0){
                sb.append(maxValue).append("#");
            }
            words[indexMax] = "";
            for(int i = 0;i < words.length;i++){
                if(words[i].length() == 0){
                    continue;
                }
                if(check(maxValue,words[i])){
                    words[i] = "";
                }
            }
            indexMax = 0;
            num--;
            flag = true;
        }

        return sb.length();
    }

    private boolean check(String s1,String s2){
        int i = s1.length()-1;
        int j = s2.length()-1;
        while(i >=0 && j >= 0){
            if(s1.charAt(i) != s2.charAt(j)){
                return false;
            }
            i--;
            j--;
        }
        return true;
    }
}

优化过的暴力法,时间复杂度就是O(n)了.

class Solution {
    public int minimumLengthEncoding(String[] words) {
        if(words.length == 0){
            return 0;
        }
        for (int i = 0; i < words.length; i++) {
            words[i] = reverse(words[i]);
        }
        Arrays.sort(words);
        int result = 0;
        for(int i = 0;i < words.length;i++){
            if(i+1 < words.length && words[i+1].startsWith(words[i])){
                continue;
            }else{
                result += words[i].length()+1;
            }
        }
        return result;
    }

    private String reverse(String string) {
        StringBuilder sb = new StringBuilder();
        for(int i = string.length()-1;i >=0 ;i--){
            sb.append(string.charAt(i));
        }
        return sb.toString();
    }
}

字典法

class Solution {
    public int minimumLengthEncoding(String[] words) {
        int result = 0;
        Trie trie = new Trie();
        //使用字典树来解决.因为长度会对结果有影响.所以需要先根据长度来给给定的字符串数组排序.
        Arrays.sort(words, Comparator.comparingInt(String::length));
        for (int i = words.length-1 ;i >= 0 ; i--) {
            result += trie.insert(words[i]);
        }
        return result;
    }
}
class Trie{
    TrieNode trieNode = new TrieNode();
    public int insert(String word){
        boolean isNew = false;
        TrieNode root = trieNode;
        for (int i = word.length()-1; i >= 0; i--) {
            if(root.trieNodes[word.charAt(i)-'a'] == null){
                root.trieNodes[word.charAt(i)-'a'] = new TrieNode();
                isNew = true;
            }
            root = root.trieNodes[word.charAt(i)-'a'];
        }
        return isNew?word.length()+1:0;
    }
}

class TrieNode{
    TrieNode[] trieNodes;

    public TrieNode() {
        trieNodes = new TrieNode[26];
    }
}