LeetCode 820. 单词的压缩编码
目录
题目描述
题意分析
题目给的是一套编码规则：把若干单词拼进一个参考串
s，再给每个单词配一个下标indices[i]，要求从s[indices[i]]一路读到下一个#恰好得到第i个单词。求s的最短长度。把规则翻译一下就清楚了：
s一定是若干段「若干字符 +#」拼起来的，每个单词必须是某一段（不含#的部分）的后缀。所以真正要决定的是「选哪些单词单独占一段」，其余单词都得搭别人的车。由此得到最关键的约束信号：能搭车的条件是「是别人的后缀」，不是前缀，也不是子串。
"me"能藏在"time#"的尾部，但"tim"就不行，因为从't'读起会读到"time"而不是"tim"。另一个约束信号是数组里允许出现重复单词。两个一模一样的单词天然共用同一个下标，只该算一次长度。
边界上要留心：只有一个单词、所有单词互不为后缀、某个单词是多个单词的公共后缀、以及输入含完全重复的单词。
解法：哈希集合删除所有后缀
核心思路
暴力做法是两两比较，对每个单词检查它是否是别的某个单词的后缀，是就丢掉，最后把剩下的长度加一累加。两两比较是 $O(n^2)$ 次，每次后缀判断还要 $O(L)$，
n到 $2000$ 时勉强能过，但写起来还得小心「一个单词不能把自己判成自己的后缀」。瓶颈在于「找谁是谁的后缀」这个方向搞反了。正向去找覆盖关系要做全体配对；反过来想，每个单词的后缀集合是可以直接列举出来的——长度为
L的单词只有 $L - 1$ 个真后缀。既然能列举，就不必配对：把所有单词丢进一个哈希集合，然后对每个单词把它的全部真后缀从集合里删掉。这样做的效果是：一个单词只要是另一个单词的真后缀，就一定会在处理那个更长单词时被删除。而删除是幂等的，重复删同一个串没有副作用。
显式的不变量是：处理完所有单词后，集合中剩下的每一个单词，都不是集合中任何其他单词的真后缀，也就是所谓的「极大单词」。这些单词必须各自单独占一段，贡献 $ w + 1$ 的长度（那个 +1就是它自己的#）；而被删掉的单词全都能挂在某个极大单词的尾巴上，一个字符也不额外花。顺带一提，哈希集合还免费解决了重复单词的问题：相同的单词进集合就自动合并成一个。
解题步骤
- 把
words全部装进一个哈希集合。装集合的第一个作用是去重，第二个作用是让后面的删除操作是常数时间。- 遍历原始的
words数组（而不是遍历集合）来枚举后缀。之所以必须遍历数组，是因为循环体里要修改集合，边遍历边删同一个容器会触发并发修改异常。- 对每个单词
word，让i从1走到word.length - 1，把word从下标i开始的后缀从集合里删掉。起点取1而不是0是关键：i = 0对应单词自己，删了就等于把这个单词也当成可省略的，答案会偏小。- 删除时不需要判断该后缀是否存在，哈希集合的删除对不存在的键是空操作。
- 遍历删干净后的集合，对每个剩余单词累加
长度 + 1。这个+1是它自己那个#，不能漏。- 返回累加结果。
以
words = ["time", "me", "bell"]走一遍：初始集合是{"time", "me", "bell"}。处理
"time"：i = 1得到后缀"ime"，集合里没有，删除无效果；i = 2得到"me"，命中，集合变成{"time", "bell"}；i = 3得到"e"，不在集合里。处理
"me"：i = 1得到"e"，不在集合里，集合不变。注意此时"me"本身已经不在集合中了，但这不影响枚举它的后缀，因为枚举的来源是数组而不是集合。处理
"bell"：依次得到"ell"、"ll"、"l"，都不在集合里，集合仍是{"time", "bell"}。最后累加：
"time"贡献 $4 + 1 = 5$，"bell"贡献 $4 + 1 = 5$，总长度是10，对应的参考串正是"time#bell#"，"me"挂在下标2上。再看重复用例
words = ["t", "t"]：集合装完只剩{"t"}，两个单词都只有一位，内层循环一次都不执行，最终返回 $1 + 1 = 2$，参考串是"t#"，两个下标都指向0。
代码实现
class Solution {
public int minimumLengthEncoding(String[] words) {
Set<String> set = new HashSet<>(Arrays.asList(words));
for (String word : words) {
for (int i = 1; i < word.length(); i++) {
set.remove(word.substring(i));
}
}
int ans = 0;
for (String word : set) {
ans += word.length() + 1;
}
return ans;
}
}
func minimumLengthEncoding(words []string) int {
set := make(map[string]bool)
for _, word := range words {
set[word] = true
}
for _, word := range words {
for i := 1; i < len(word); i++ {
delete(set, word[i:])
}
}
ans := 0
for word := range set {
ans += len(word) + 1
}
return ans
}
复杂度分析
- 时间复杂度：$O(nL^2)$，
n是单词个数，L是单词最大长度。每个单词产生 $L - 1$ 个后缀，每个后缀的切分和哈希都要 $O(L)$，题目限定 $L \le 7$，所以实际接近线性。- 空间复杂度：$O(nL)$，哈希集合最多存下全部
n个单词，每个单词占 $O(L)$ 字符；枚举后缀时临时构造的子串会被立刻回收，不叠加。
关键点总结
- 当「找出谁被谁覆盖」难做时，试试反过来「把所有可能的被覆盖者删掉」。这题的后缀集合是可枚举且规模很小的，反向删除把 $O(n^2)$ 的两两配对降成了对每个单词的常数次哈希操作。
- 把题面的操作规则先翻译成一句结构性判断（「每个单词必须是某段的后缀」），再翻译成一个集合性质（「留下的都是极大单词」），是这类构造题的标准解法路径。直接对着
indices和#硬想很容易卡住。- 哈希集合在这里一鱼两吃：既做去重，又做删除标记。识别出「重复单词天然共用下标」这个隐含条件，比补一段专门的去重代码更干净。
- 修改容器和遍历容器必须分开。这里遍历原数组、修改集合，是回避并发修改问题最省事的写法。
- 面试视角：面试官大概率会追问 Trie 解法。标准答案是把每个单词反过来插进一棵字典树，然后统计所有叶子节点的深度加一之和，复杂度同样是 $O(nL)$ 但不依赖哈希，且在
L很大时优势明显。能主动说出「后缀问题就把串反过来变成前缀问题」这句转化，是这题的加分项。- 面试视角：说清
+1是分隔符#、说清i从1起是为了排除单词自身，这两个细节比整体思路更能反映有没有真的写过一遍。
易错点总结
- 错误写法：枚举后缀时让
i从0起，把单词自己也删掉。用例["time", "me", "bell"]→ 处理"time"时先把"time"自己删了，处理"bell"时也一样，集合最后空掉，返回0而不是10。- 错误写法：不去重，直接遍历数组累加长度加一。用例
["me", "me"]→ 两个相同单词各算一次得6，而它们共用同一个下标，正确答案是3。- 错误写法：把覆盖关系当成前缀关系，枚举
word.substring(0, i)。用例["time", "me", "bell"]→ 删掉的是"t"、"ti"、"tim"之类，"me"一直留在集合里，返回 $5 + 3 + 5 = 13$ 而不是10。- 错误写法：一边遍历集合一边从集合里删元素。用例
["time", "me"]→ 处理"time"时删掉了"me"，迭代器随即失效，Java 抛出ConcurrentModificationException。- 错误写法：累加时只加单词长度，漏掉分隔符。用例
["time", "bell"]→ 返回4 + 4 = 8，而每段结尾都需要一个#，正确答案是10。- 错误写法：只删掉去掉首字符后的那一个后缀，不枚举全部真后缀。用例
["time", "me"]→ 只删了"ime"，"me"留在集合里，返回 $5 + 3 = 8$ 而不是5。- 错误写法：认为更长的单词必然覆盖更短的，按长度排序后只保留最长的那个。用例
["time", "bell"]→ 两者长度相同且互不为后缀，各自都要单独编码，正确答案是10，只留一个会返回5。- 错误写法：改用两两
endsWith判断却忘了排除自己和自己比。用例["time"]→"time".endsWith("time")为真，唯一的单词被判成可省略，返回0而不是5。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 065. 单词的压缩编码 | 中等 | 同题的另一入口，适合对照哈希删除与反向 Trie 两种写法 |
| 208. 实现 Trie (前缀树) | 中等 | 手写字典树的插入与查询，是本题 Trie 解法的前置基本功 |
| 648. 单词替换 | 中等 | 在字典树上找最短前缀匹配，方向与本题的后缀覆盖相反 |
| 14. 最长公共前缀 | 简单 | 同为一组字符串的公共结构，但只需纵向逐列比较 |