LeetCode LCR 065. 单词的压缩编码
目录
题目描述
题意分析
要把一批单词编码成一个字符串
s和一组下标：从某个下标出发，读到第一个#为止，恰好还原出对应的单词。问这个s最短能有多长。编码规则里的「读到
#为止」是唯一的信息来源。它意味着一个单词占据的是s中「以#结尾的一段」，因此如果单词A是单词B的后缀，那么B写进s之后，A不需要再写——从B内部靠后的某个位置起读，读到B的那个#，得到的正是A。反过来，前缀关系毫无用处，因为读取必须一直读到#。所以问题被翻译成：把所有「是别的单词的后缀」的单词删掉，剩下的单词各自写一遍并各带一个
#，答案就是这些单词的长度之和再加上它们的个数。约束是单词数到 2000、单词长度到 7，字符集为小写字母。长度极短说明后缀的数量很少（每个单词至多 7 个后缀），既可以用哈希枚举后缀，也可以用树形结构统一处理；单词数 2000 说明两两比较的 $O(n^2 L)$ 也不至于超时，但不是好答案。
边界上要注意：输入可能含完全重复的单词，重复项互为后缀只应计一次；一个单词可能同时是多个单词的后缀，也只删一次；不存在任何后缀关系时，答案就是所有单词长度加上单词数。
解法：哈希表统计状态
核心思路
暴力做法是两两比较，判断
words[i]是否为words[j]的后缀，把所有被包含的单词标记删除。代价 $O(n^2 L)$，在 $n = 2000$ 时是 $2.8 \times 10^7$ 次字符比较，勉强能过，但它把「后缀」当成一个个孤立的判定，没有利用后缀之间的共享结构。瓶颈在于同一个后缀关系会被反复验证：
"me"、"ime"、"time"三者的比较里，"me"这一段被扫了很多遍。而后缀关系本质上是有传递性和共享性的，和前缀完全对称。观察的关键一步：把每个单词反过来插入，后缀关系就变成前缀关系。
"me"是"time"的后缀，等价于"em"是"emit"的前缀。而前缀关系正是 Trie 天生擅长表达的——共享前缀的单词共享一段路径。于是把所有单词倒序插入一棵 Trie。插入完成后，一个单词「不是任何其它单词的后缀」当且仅当它在树中的终点是叶子节点（没有任何子节点）：若它还有子节点，说明存在某个更长的反串以它为前缀，也就是存在某个更长的原串以它为后缀，它可以被省略掉。
由此得到状态定义：对树中每个节点，定义
dfs(node, depth)为「以该节点为根的子树中，所有叶子对最终答案的贡献之和」，其中depth是该节点在树中的深度（根为 1 时，深度恰好等于「该节点代表的字符串长度 + 1」，那个 +1 正是这个单词要带的#）。叶子节点直接贡献depth，内部节点把所有子树的贡献相加。维持的不变量是：答案只由叶子决定，内部节点一律不计费。这一条自动完成了三件事——去掉被后缀包含的单词、给每个保留的单词加上恰好一个
#、对重复单词自动去重（重复插入走同一条路径，只产生一个叶子）。
解题步骤
- 定义只含 26 个子指针的 Trie 节点。这里不需要
isEnd标记，因为判定条件是「有没有子节点」而不是「是不是某个单词的终点」，结束信息对本题无用。- 对每个单词，从最后一个字符往前逐个插入。倒序插入是整题的转折点，它把后缀包含转成前缀共享；正序插入得到的是前缀关系，与题意完全不符。
- 插入时子节点为空则新建，然后下移。重复的单词第二次插入时不会新建任何节点，天然去重。
- 从根出发做深度优先搜索，携带当前深度，根的深度取 1。取 1 而不是 0，是因为每个保留下来的单词除了自身长度还要占一个
#，把这个偏移直接放进初始深度，就不必在叶子处额外加一。- 在每个节点扫描 26 个子指针：只要存在非空子节点，就说明它不是叶子，递归累加子树的贡献。
- 若 26 个子指针全空，说明当前节点是叶子，把当前深度累加进答案。深度此刻恰好等于「这条路径代表的单词长度 + 1」，也就是这个单词在
s中占的格子数。- 返回根的累加结果即为答案。
以
words = ["time", "me", "bell"]走一遍：倒序插入得到三条路径e→m→i→t、e→m、l→l→e→b。插入"time"时新建 4 个节点；插入"me"时e、m都已存在，一个新节点都不建，它的终点是"emit"路径中间的m；插入"bell"时新建 4 个节点。深搜从根（深度 1）开始：走e（深度 2）→m（深度 3，注意它有子节点i，不是叶子，"me"因此一分不计）→i（深度 4）→t（深度 5，无子节点，是叶子，贡献 5，对应"time#"的五个格子）。再走另一支l（2）→l（3）→e（4）→b（5，叶子，贡献 5，对应"bell#"）。总和 10，正是"time#bell#"的长度。
代码实现
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(\sum L_i + 26 \cdot C)$，其中 $\sum L_i$ 是插入所有单词的字符总数，$C$ 是树中节点数（不超过字符总数），深搜在每个节点固定扫描 26 个子指针。本题 $L \le 7$、$n \le 2000$，总量极小。
- 空间复杂度：$O(26 \cdot C)$，每个节点携带长度 26 的指针数组，加上深搜的递归栈 $O(L)$，共享后缀的单词不重复占用节点。
关键点总结
- 「后缀关系」倒序之后就是「前缀关系」，而前缀关系有现成的结构可用。遇到后缀、逆序、从右往左的约束，先试着把串反过来，往往能直接套用已有工具。
- 判定「不被别人包含」的标准落在叶子上，而不是落在「单词终点标记」上。想清楚答案由哪类节点决定，能省掉一整套无用的状态位。
- 把
#的开销折进初始深度（根记为 1），比在叶子处写answer += l + 1更不容易漏加漏减，这是常数偏移的常见处理技巧。- Trie 插入天然去重：重复单词走同一条路径、只产生一个叶子，不必额外用集合预处理。
- 前缀关系在本题完全无用——只有后缀能被共享。做题时要先确认编码规则锚定的是哪一端，方向错了整个结构就白搭。
- 面试视角：开场先把题意翻译成「删掉所有是别的单词后缀的单词，答案 = 剩余单词长度和 + 剩余单词数」，这一步翻译就已经拿到大半分；之后无论用哈希枚举后缀还是用反向 Trie，都是实现细节。
- 面试视角：常见追问是「不用 Trie 怎么做」。答把所有单词放进哈希集合，再对每个单词枚举它的全部真后缀并从集合中移除，最后统计集合中剩余单词，复杂度 $O(n L^2)$，在 $L$ 很小时反而更简洁。
易错点总结
- 错误写法：正序插入单词，按前缀关系判定。用例
words = ["time", "me"]→"me"与"time"在树中毫无关系，两个都被当成叶子，答案算成 8，正确答案是 5。- 错误写法：深搜初始深度传 0。用例
words = ["time"]→ 叶子深度为 4，答案算成 4，正确答案是 5，漏掉了结尾的#。- 错误写法：在叶子处贡献
l的同时，内部节点也累加自身深度。用例words = ["time", "me"]→ 中间节点被计费，答案偏大，正确答案只由叶子决定。- 错误写法：给节点加
isEnd标记，按「是某个单词终点」而非「是叶子」来计费。用例words = ["time", "me"]→"me"的终点标记为真也被计一次，答案算成 8，正确答案是 5。- 错误写法：先用集合给单词去重，却在插入时仍按原数组遍历并把节点数当答案。用例
words = ["time", "time"]→ 若把「新建节点数」当答案会得到 4，正确答案是 5；答案要按叶子深度算，而不是按节点数算。- 错误写法：判断叶子时写成「第一个子指针为空即为叶子」。用例
words = ["bell"]→ 反串"lleb"的根子节点是l，下标 11，下标 0 处为空于是根被误判成叶子，直接返回 1，正确答案是 5。- 错误写法：把后缀判断写成
contains子串包含。用例words = ["time", "im"]→"im"是"time"的子串但不是后缀，被错误删除，答案算成 5，正确答案是 8。- 错误写法：认为只需删除完全相同的重复单词，不处理后缀包含。用例
words = ["me", "time"]→ 答案算成 8，正确答案是 5。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 820. 单词的压缩编码 | 中等 | 与本题同题，可用来对照反向 Trie 与哈希枚举后缀两种写法 |
| 208. 实现 Trie (前缀树) | 中等 | 只做插入与查询，判定落在终点标记而非叶子，是本题的结构基础 |
| 648. 单词替换 | 中等 | 锚点在前缀且要取最短，靠首次命中提前退出而非统计叶子 |
| 720. 词典中最长的单词 | 中等 | 需要整条路径上每个前缀都是单词，判定沿路径累积 |
| 745. 前缀和后缀搜索 | 困难 | 前后缀同时约束，靠拼接复合键把两端条件压成一次查询 |
| 1044. 最长重复子串 | 困难 | 同样围绕子串共享结构，但需要二分答案配合字符串哈希 |
| 面试题 08.04. 幂集 | 中等 | 同为「枚举全部子结构」，但走的是回溯而非树上共享路径的思路 |