给定一个单词列表我们将这个列表编码成一个索引字符串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] 。
提示
解题思路
这个问题是Leetcode 943最短超级串简化版通过观察可以发现在这个问题中如果一个字符串是另一个字符串的后缀那么可以将这两个字符串进行合并合并的同时记录两个字符串的起始位置并且结束位置添加#。例如
timeme-----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.rootfor c in word:if c not in cur.next:# herecur.next[c] Node()cur cur.next[c]self.nodes[cur] iclass Solution:def minimumLengthEncoding(self, words: List[str]) -> int:root Trie()for i, word in enumerate(words):root.insert(word[::-1], i)res 0for k, v in root.nodes.items():if k.next: continue # 后面还有节点那么就不是叶子res len(words[v]) 1return 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) 1for 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
如有问题希望大家指出