Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

单词的压缩编码

Posted on In , ,
Symbols count in article: 2.2k Reading time ≈ 2 mins.

来自Leetcode第820题单词的压缩编码

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

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

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

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

示例：

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

遍历

题目的意思大概就是将输入里的字符串按某种方式编码，最后返回编码字符串的长度，考虑到字符串S可能是字符串T的后缀，这样的话字符串S就不用加入到编码字符串里了，于是可以考虑先将字符串按长度排序，字符串长的排在前面，如果遍历到的字符串i在包含在原本的字符串里，则不加入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int minimumLengthEncoding(String[] words) {
     //先按长度倒叙，长的在前面，保证能够框住后面的字符。
    Arrays.sort(words, (a1,a2)-> a2.length() - a1.length());

    StringBuffer result = new StringBuffer();
    result.append(words[0]+"#");
    int total  = result.length();
    for(int i=1; i< words.length;i++){
        //如果前面的字符包含了后面的字符，则个数不变，否则加上后面字符长度
        if(result.indexOf(words[i]+"#")<0){
            result.append(words[i] + "#");
            total = total +1 + words[i].length();
        }
    }
    return total ;
}

翻转字符串

来自nettee

string-suffix-tree

可以看到，字符串 me 的路径已经完全和 time 重合了，而 lime 和 time 只是部分重合。我们只需要把所有有自己独立起点的字符串作为编码字符串就可以了。

其实这道题我们的思路很简单：如果有一对单词 s 和 t，使得 t 是 s 的后缀，例如 me 是 time 的后缀，我们就删掉单词 t。最后剩下来的单词，就是构成索引字符串的单词。

那么，如何找到这些 s 和 t 呢？考虑到 s 和 t 的最后几个字母是一样的，我们可以从单词的最后一个字母向前考虑。先把所有的单词按照最后一个字母分成 26 组，这样 s 和 t 肯定在同一组；再在每一个组中按照倒数第二个字母分成 26 组……

我们发现这样排序太麻烦，不如直接把所有单词反转（reverse），让倒的变成正的。Amazing！所有单词反转之后，我们的单词排序规则变成了字典顺序，也就是各种语言中比较字符串的默认顺序。

不信你看，假设我们将 ["time", "me", "lime", "sometime", "hell", "shell"] 几个单词反转后排序：

process

我们发现，如果 t 是 s 的后缀，那么反转之后 t’ 就是 s’ 的前缀。在反转+排序之后，s’ 一定紧跟在 t’ 的后面！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int minimumLengthEncoding(String[] words) {
    int len = words.length;
    //从字符串高位开始遍历排序
    Arrays.sort(words, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            int len1 = o1.length();
            int len2 = o2.length();
            char[] arry1 = o1.toCharArray();
            char[] arry2 = o2.toCharArray();
            for(int i = 0 ; i < Math.min(len1,len2);++i){
                int c = Character.compare(arry1[len1 - 1 - i],arry2[len2 - 1 - i]);
                if(c != 0)
                    return c;
            }
            return Integer.compare(len1,len2);
        }
    });
    int ans = 0 ;
    for(int i = 0 ; i < len ; ++i){
        if(i + 1 < len && words[i+1].endsWith(words[i])) {
        }
        else
            ans += words[i].length()+1;  //加上'#'的长度
    }
    return ans;
}

字典树

见sweetiee