Py学习  »  Python

leetcode每日一题 python解法 3月28日

Never肥宅 • 4 年前 • 193 次点击  

难度:中等

题目内容:

给定一个单词列表,我们将这个列表编码成一个索引字符串 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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/57112
 
193 次点击