Leetcode 820:单词的压缩编码(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 820:单词的压缩编码(超详细的解法!!!)

in leetcode with 0 comment

给定一个单词列表,我们将这个列表编码成一个索引字符串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. 1 <= words.length <= 2000
  2. 1 <= words[i].length <= 7
  3. 每个单词都是小写字母 。

解题思路

这个问题是Leetcode 943:最短超级串简化版,通过观察可以发现,在这个问题中,如果一个字符串是另一个字符串的后缀,那么可以将这两个字符串进行合并,合并的同时记录两个字符串的起始位置,并且结束位置添加'#'。例如:

time
  me
-----
time#  起始位置:[0, 2]

我们希望最后得到的字符串长度最短,那么就希望尽可能合并的字符串较长,这明显就是Trie的性质了Leetcode 208:实现 Trie (前缀树)(只需要将字符串反转即可使用Trie)。最后统计Trie所有叶子节点深度+1(添加"#")的和就是我们的结果。

叶子节点的判断有两种思路:1)所有单词插入结束后,dfs判定叶子节点。 2)每插入一个单词,记录最后字符(很可能就是叶子),然后遍历所有记录的叶子,如果其后没有节点,那它确实就是叶子节点了。

class Node:
    def __init__(self):
        self.next = dict()
        
class Trie:
    def __init__(self):
        self.root = Node()
        self.nodes = dict()

    def insert(self, word, i):
        cur = self.root
        for c in word:
            if c not in cur.next:    # here
                cur.next[c] = Node()
            cur = cur.next[c]
            
        self.nodes[cur] = i

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        root = Trie()
        for i, word in enumerate(words):
            root.insert(word[::-1], i)

        res = 0
        for k, v in root.nodes.items():
            if k.next: continue # 后面还有节点,那么就不是叶子
            res += len(words[v]) + 1
        return res

pythonic的写法:

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        words = list(set(words)) 
        Trie = lambda: collections.defaultdict(Trie)
        trie = Trie()
        
        # trie[S[0]][S[1]][S[2]][...][S[S.length - 1]]
        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)

reference:

https://leetcode-cn.com/problems/short-encoding-of-words/solution/dan-ci-de-ya-suo-bian-ma-by-leetcode-solution/

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses