[LeetCode] 820. 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].

Note:

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

单词的压缩编码。

题意是给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。请返回编码的长度。

题目描述给的非常模糊，我拿例子解释一下，在input的数组里面有若干个单词，其中有一些词有可能是其他词的后缀，比如me就是time的后缀。题目只要求返回编码的长度10，而不需要返回对应的index所以会简单很多。这个题有两种做法，一种是用hashset，一种是用trie前缀树。我只能解释清楚第一种思路，前缀树的解法之后再补。题目中有提示到input里面单词的长度最长为7所以还勉强可以用hashset做。思路如下，

1. 用hashset存住input里面的每个单词

2. 遍历每个单词，看每个单词的每个substring后缀是否在hashset中存在，若存在就删除。比如还是time和me的例子吧，当扫描到time的后缀me的时候，发现me这整个单词在hashset里存在，所以可以直接将其删去，因为他一定不是编码的一部分。

3. 再次扫描hashset，因为此时去掉了所有可以当后缀的词，所以只需要累加所有hashset里面的元素的长度即可。

时间O(n^2) = O(number of words) * O(substring)

空间O(n) - hashset

Java实现

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Set<String> good = new HashSet(Arrays.asList(words));
        for (String word : words) {
            for (int k = 1; k < word.length(); k++) {
                good.remove(word.substring(k));
            }
        }
        int res = 0;
        for (String word : good) {
            res += word.length() + 1;
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {string[]} words
 * @return {number}
 */
var minimumLengthEncoding = function(words) {
    let hashSet = new Set(words);
    for (let item of hashSet) {
        for (let i = 1; i < item.length; i++) {
            let target = item.slice(i);
            hashSet.has(target) && hashSet.delete(target);
        }
    }
    let res = 0;
    hashSet.forEach(item => (res += item.length + 1));
    return res;
};

LeetCode 题目总结