「LeetCode每日一题」——820. 单词的压缩编码

`820. 单词的压缩编码`

链接：https://leetcode-cn.com/problems/short-encoding-of-words/ 难度：中等

`题目`

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

`思路`

做NLP的人，应该很熟悉Trie树。今天的题目我们用它来解决。

根据题意，如果一个单词是另外一个单词的后缀的话，那其实可以通过索引的方式来得到，这样就被压缩掉了。注意，这里是整个单词，非单词的一部分。所以，我们的目的就是找到所有不是其他单词后缀的单词，然后单词长度+1，总和就是答案。

先介绍一下Trie树。Trie，也叫字典树，前缀树。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

举个例子：我们有6个字符串，它们分别是：how，hi，her，hello，so，see，那我们构建的Trie树如下图所示。

这道题我们求的是后缀，所以需要把字符串反序之后插入到Trie树种，Trie树的叶子节点就是没有后缀的单词，我们统计一下长度+1就可以了。

代码见解决方案。

`方案代码`

解决方案：

from collections import defaultdict
class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        words = list(set(words))
        Trie = lambda: defaultdict(Trie)
        trie = Trie()

        nodes = [reduce(dict.__getitem__, word[::-1], trie) for word in words]

        return sum(len(word) + 1 for i, word in enumerate(words) if len(nodes[i]) == 0)

「LeetCode每日一题」——820. 单词的压缩编码

820. 单词的压缩编码

题目

思路

方案代码

相关

相关推荐

`820. 单词的压缩编码`

`题目`

`思路`

`方案代码`