820. 单词的压缩编码
单词数组
words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：words.length == indices.length
- 助记字符串
s以'#'字符结尾
- 对于每个下标
indices[i]，s的一个从indices[i]开始、到下一个'#'字符结束（但不包括'#'）的 子字符串 恰好与words[i]相等
给你一个单词数组
words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。示例 1：
输入：words = ["time", "me", "bell"] 输出：10 解释：一组有效编码为 s ="time#bell#" 和 indices = [0, 2, 5] 。 words[0] = "time" ，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#" words[1] = "me" ，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#" words[2] = "bell" ，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
示例 2：
输入：words = ["t"] 输出：2 解释：一组有效编码为 s = "t#" 和 indices = [0] 。
提示：
1 <= words.length <= 2000
1 <= words[i].length <= 7
words[i]仅由小写字母组成
通过次数60,222提交次数117,489
法 1 前缀树
思路
根据题目意识，可以转化为求前缀树各路径长度之和。
题解
class Node: def __init__(self): self.child = {} self.is_word = None class TrieTree: def __init__(self): self.root = Node() def add(self, word): node = self.root for char in word: if char not in node.child: node.child[char] = Node() node = node.child[char] node.is_word = True class Solution: def minimumLengthEncoding(self, words: List[str]) -> int: t =TrieTree() for w in words: t.add(w[::-1]) self.res = [] # 计算 从根节点 到各自节点的路径长度 self.dfs(t.root, length=0) return sum(self.res) + len(self.res) def dfs(self, node, length): if len(node.child) == 0: self.res.append(length) return for char, char_node in node.child.items(): self.dfs(char_node, length+1)