亲宝软件园·资讯

展开

leetcode之820. 单词的压缩编码 | python极简实现字典树

ManWingloeng 人气:0
# 题目 给定一个单词列表,我们将这个列表编码成一个索引字符串 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 每个单词都是小写字母 。 ``` https://leetcode-cn.com/problems/short-encoding-of-words 今天leetcode的每日一题的官方题解的python解法惊艳到我了,代码十分Pythonic,正好我也不太熟悉字典树和reduce的用法,学了一下: 简单的来说就是:一句话实现字典树,一句话完成建树过程。 ![](https://img2020.cnblogs.com/blog/1653638/202003/1653638-20200328210619706-952795831.png) ```python 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) ``` `Trie = lambda: collections.defaultdict(Trie)`这个循环嵌套字典是类似这样的效果{{{{}}}},意思是只要没有key的我们就返回一个空字典。 **其实字典树的本质就是循环嵌套字典。** `trie[word[-1]][word[-2]].........`是写成这样了`reduce(dict.__getitem__, word[::-1], trie)` 下面给出[@Lucien](https://leetcode-cn.com/u/lucien_z/)在leetcode题解下的[评论解释](https://leetcode-cn.com/problems/short-encoding-of-words/solutionhttps://img.qb5200.com/download-x/dan-ci-de-ya-suo-bian-ma-by-leetcode-solution/316724/) 关于Python字典树方法的解释: 我们需要一棵字典树,把所有word加入这棵树 找到所有叶子的高度和 一步步从最正常的写法走向Pythonic的解。 ```python # 定义字典树中的一个节点 class Node(object): def __init__(self): self.children={} class Solution: def minimumLengthEncoding(self, words: List[str]) -> int: words = list(set(words)) #需要去重,否则在之后计算“叶子高度”的时候会重复计算 trie=Node() #这是字典树的根 nodes=[] #这里保存着每个word对应的最后一个节点,比如对于单词time,它保存字母t对应的节点(因为是从后往前找的) for word in words: now=trie for w in reversed(word): if w in now.children: now=now.children[w] else: now.children[w]=Node() now=now.children[w] nodes.append(now) ans=0 for w,c in zip(words,nodes): if len(c.children)==0: #没有children,意味着这个节点是个叶子,nodes保存着每个word对应的最后一个节点,当它是一个叶子时,我们就该累加这个word的长度+1,这就是为什么我们在最开始要去重 ans+=len(w)+1 return ans ``` 相信以上的解答大家可以看懂,那么就从Node开始简化。原先我们把Node声明为一个类,但这个类中只有一个字典,所以我们不如就直接用一个字典来表示节点,一个空字典以为着这是一个叶子节点,否则字典中的每一个元素都是它的一个孩子,上面的代码可以简化为: ```python class Solution: def minimumLengthEncoding(self, words: List[str]) -> int: words = list(set(words)) #需要去重,否则在之后计算“叶子高度”的时候会重复计算 trie={} #这是字典树的根 nodes=[] #这里保存着每个word对应的最后一个节点,比如对于单词time,它保存字母t对应的节点(因为是从后往前找的) for word in words: now=trie for w in reversed(word): if w in now: now=now[w] else: now[w]={} now=now[w] nodes.append(now) ans=0 for w,c in zip(words,nodes): if len(c)==0: #一个空字典,意味着这个节点是个叶子 ans+=len(w)+1 return ans ``` 继续简化,我们不想在生成字典树时每次都判断“当前字典有没有这个键”,我们希望,有这个键,就返回它的值,否则返回一个空字典给我。很自然,我们需要用到defaultdict,它默认返回一个字典。但,只是返回一个普通字典吗?比如defaultdict(dict)? 不行,实际上它需要返回一个defaultdict,且这个defaultdict仍旧会递归地返回defaultdict。于是,递归地,我们定义这样一个函数,它返回一个defaultdict类型,且它的默认值是该类型本身。 Trie = lambda: collections.defaultdict(Trie) ,注意,这里的Trie是一个函数,它返回一个defaultdict实例。有了它,我们创建字典树的过程就变成了: ```python nodes=[] Trie = lambda: collections.defaultdict(Trie) trie = Trie() for word in words: now=trie for w in word[::-1]: now=now[w] nodes.append(now) ``` 更进一步,可以简化为 ```python nodes=[] Trie = lambda: collections.defaultdict(Trie) trie = Trie() for word in words: nodes.append(trie[word[-1]][word[-2]].........) ``` 它就变成了 ```python nodes = [reduce(dict.__getitem__, word[::-1], trie) for word in words] ``` 先不管数组的推导式,单看数组的一项 reduce(dict.__getitem__, word[::-1], trie),reduce三个参数分别为:方法,可循环项,初始值。即它初始值是trie,按照word[::-1]的循环顺序,每次去执行方法dict.__getitem__,且将这个输出作为下次循环的输入,所以它就是trie[word[-1]][word[-2]].........的意思。 最后一步的sum很简单,只要大家明白nodes里存的是什么就很明显了。 另外附上标准的C++写法: ```C++ class TrieNode{ TrieNode* children[26]; public: int count; TrieNode() { for (int i = 0; i < 26; ++i) children[i] = NULL; count = 0; } TrieNode* get(char c) { if (children[c - 'a'] == NULL) { children[c - 'a'] = new TrieNode(); count++; } return children[c - 'a']; } }; class Solution { public: int minimumLengthEncoding(vector& words) { TrieNode* trie = new TrieNode(); unordered_map nodes; for (int i = 0; i < (int)words.size(); ++i) { string word = words[i]; TrieNode* cur = trie; for (int j = word.length() - 1; j >= 0; --j) cur = cur->get(word[j]); nodes[cur] = i; } int ans = 0; for (auto& [node, idx] : nodes) { if (node->count == 0) { ans += words[idx].length() + 1; } } return ans; } }; ```

加载全部内容

相关教程
猜你喜欢
用户评论