🥈medium

🥈Medium
题解
- 方法一：存储后缀
- 方法二：字典树

给定一个单词列表，我们将这个列表编码成一个索引字符串 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
每个单词都是小写字母

题解

十个月前做过的题目，今天再拿起来又不会了。这种接连失败的状态什么时候可以到头。真的好想努力之后能看到好的结果🙏🙏🙏。

方法一：存储后缀

如果单词X是Y的后缀，那编码Y的时候就同时将X编码了。如果单词X不在任何单词Y的后缀中出现，那X一定是编码字符串的一部分。
因此，目标就是保留所有不是其他单词后缀的单词，最后的结果就是这些单词长度加一的总和（每个单词后需加#）

Python

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        good = set(words)
        for word in words:
            for k in range(1, len(word)):
                good.discard(word[k:])
        return sum(len(word) + 1 for word in good)

JavaScript

/**
 * @param {string[]} words
 * @return {number}
 */
var minimumLengthEncoding = function(words) {
    const wordSet = new Set(words)
    for (let i in words){
        for(let j = 1;j<words[i].length;j++){
            wordSet.delete(words[i].slice(j))
        }
    }
    let sum=0
    wordSet.forEach(item => sum+=item.length+1)
    return sum
};

复杂度分析

时间复杂度：，其中是word[i]的长度。每一个单词有个后缀，对于每个后缀，查询其是否在集合中需要的哈希值计算
空间复杂度：，存储单词的空间开销

方法二：字典树

目的就是保留所有不是其他单词后缀的单词。可以去找到是否不同的单词具有相同的后缀，我们可以将其反序之后插入字典树中。这样emit和em才有前缀关系，直接用time和me是没有前缀关系的。例如，我们有 “time” 和 “me”，可以将 “emit” 和 “em” 插入字典树中。