难度：中等

题目内容：

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

题解：

从例子中可以看出来，需要在用#把单词隔开的同时，把"me"这样的单词包含进"time"中，尽量减少长度。

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        wordList = ""
        words.sort(key = lambda i:len(i),reverse=True)  # 排序单词（按照长度,最长在前）
        for word in words:
            if not word + "#" in wordList:
                wordList += word
                wordList += "#"
        return len(wordList)

好像蛮简单的，但是性能贼垃圾

image.png

官方提供了字典树的方法，学数据结构还是了解一下比较好
大概就是把词根末尾的字幕逐个插入
这样最后的每个叶子节点就是所有的独特后缀单词，把每个叶子节点的深度相加就可以了

image.png

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        words = list(set(words)) #remove duplicates
        #Trie is a nested dictionary with nodes created
        # when fetched entries are missing
        Trie = lambda: collections.defaultdict(Trie)
        trie = Trie()

        #reduce(..., S, trie) is trie[S[0]][S[1]][S[2]][...][S[S.length - 1]]
        nodes = [reduce(dict.__getitem__, word[::-1], trie)
                 for word in words]

        #Add word to the answer if it's node has no neighbors
        return sum(len(word) + 1
                   for i, word in enumerate(words)
                   if len(nodes[i]) == 0)

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/short-encoding-of-words/solution/dan-ci-de-ya-suo-bian-ma-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。