LeetCode LCR 065. 单词的压缩编码
题目描述
题意分析
把所有单词编码进一个以
#结尾的字符串。每个单词都能从某个起始下标读到下一个#，并在去掉#后恰好得到原词。只需返回最短编码长度，不要求构造编码串和下标数组。若一个单词是另一个单词的后缀，就可以共用后者的结束符，从其内部开始读取，无需再单独写一份。前缀或中间子串没有这种性质，因为读取会一直持续到下一个
#。重复单词也只需编码一次。
解法：反向 Trie 合并公共后缀
核心思路
[!blue]
先考虑哪些单词必须保留。去掉重复项后，若一个词是其他更长词的后缀，可以省略它；沿着更长词继续查找，最终一定能由一个不再被包含的词覆盖。把这些保留词分别加上
#后拼接，就能表示所有输入单词。这个构造已经最短：两个互不构成后缀关系的保留词，不能共用同一个结束
#，否则它们的读取位置前后排列，较短者必然是较长者的后缀。不同结束符对应的单词片段又被#隔开，所以每个保留词至少需要自己的长度加一个结束符。逐词拼接恰好达到这个总长度下界。为高效找出被后缀包含的词，将每个单词从最后一个字符向前插入 Trie。原串的后缀关系反转后变成前缀关系：较短词的反向路径如果还能继续向下，就说明某个更长词以它为后缀。
所有单词插入完成后，叶子节点恰好代表需要单独编码的词。叶子一定是某个插入单词的终点，否则创建路径时还会继续产生孩子；有孩子的单词终点则已经被更长词覆盖。因此这里只检查有无孩子，不需要
isEnd标记。重复单词走相同路径，也只产生同一个叶子。代码用
dfs(cur, l)累加子树中的叶子贡献，其中l等于根到当前节点的字符数加一。根从l = 1开始，每下降一层加一；叶子直接贡献l，正好包括词长和一个#；内部节点只累加各孩子的返回值。题目保证至少有一个非空单词，所以根不会成为需要计费的叶子。扫描完所有子树后，各保留词各贡献一次，返回值就是上述最短长度。
解题步骤
- 创建包含 $26$ 个子指针的 Trie 根节点。
- 对每个单词倒序遍历字符，复用已有路径，仅在缺少孩子时创建节点。
- 从根调用
dfs(root, 1)，递归时把l加一。- 存在孩子时累加所有孩子的贡献；没有孩子时返回当前
l。- 返回根的累加结果。
代码实现
class Trie {
Trie[] children = new Trie[26];
}
class Solution {
public int minimumLengthEncoding(String[] words) {
Trie root = new Trie();
for (String w : words) {
Trie cur = root;
for (int i = w.length() - 1; i >= 0; i--) {
int idx = w.charAt(i) - 'a';
if (cur.children[idx] == null) {
cur.children[idx] = new Trie();
}
cur = cur.children[idx];
}
}
return dfs(root, 1);
}
private int dfs(Trie cur, int l) {
boolean isLeaf = true;
int answer = 0;
for (int i = 0; i < 26; i++) {
if (cur.children[i] != null) {
isLeaf = false;
answer += dfs(cur.children[i], l + 1);
}
}
if (isLeaf) {
answer += l;
}
return answer;
}
}
type trie struct {
children [26]*trie
}
func minimumLengthEncoding(words []string) int {
root := new(trie)
for _, w := range words {
cur := root
for i := len(w) - 1; i >= 0; i-- {
if cur.children[w[i]-'a'] == nil {
cur.children[w[i]-'a'] = new(trie)
}
cur = cur.children[w[i]-'a']
}
}
return dfs(root, 1)
}
func dfs(cur *trie, l int) int {
isLeaf, answer := true, 0
for i := 0; i < 26; i++ {
if cur.children[i] != nil {
isLeaf = false
answer += dfs(cur.children[i], l+1)
}
}
if isLeaf {
answer += l
}
return answer
}
复杂度分析
- 时间复杂度：$O(S+26C)$，
S为输入单词总字符数，C为包含根在内的 Trie 节点数，满足 $C\le S+1$。插入访问每个输入字符，深搜在每个节点检查固定 $26$ 个孩子。- 空间复杂度：$O(26C)$ 存储树节点，另有深度为最长单词长度加一的递归栈；重复词和公共反向前缀会复用节点。
关键点总结
[!green]
- 能省略的是完整地成为另一词后缀的单词，只有部分公共后缀并不代表两个词可以共用一个结束符。
- 倒序插入将后缀包含变成路径包含，叶子对应必须独立编码的单词。
l包含结束符的一个单位，根从 $1$ 开始，叶子无需再额外加一。- 编码构造达到每个保留词至少占“词长加一”的下界，因此最优。
易错点总结
[!yellow]
- 正序插入识别的是前缀包含，不能解决以结束符为界的后缀共享。
- 把内部的单词终点也计费，会重复计算已被更长词覆盖的后缀。
- 叶子贡献必须包括一个
#；当前代码已把它计入初始深度，不能再重复增加。- 按输入出现次数累加会重复计算相同单词，应依靠共享路径后的叶子统计。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 208. 实现 Trie (前缀树) | 中等 | 把单词倒序插入Trie，使共同后缀转成共同前缀，最终只计没有被其他词包含的叶子。 |