LeetCode 820. 单词的压缩编码
题目描述
题意分析
构造参考串，使每个单词都能从某个下标开始，一直读取到后面的第一个
#，恰好得到这个单词。不同单词可以共用同一段编码，重复单词也可以共用同一个下标。本题只求参考串的最短长度，不要求返回参考串或下标数组。
解法：哈希集合删除所有后缀
核心思路
[!blue]
单词必须一直读到
#才结束，因此一个单词能直接借用另一个单词的编码，当且仅当它是后者的后缀。只出现在开头或中间还不够，后面多出的字符也会被读入。先用集合去重，再对每个原单词枚举所有真后缀，将这些后缀从集合中删除。真后缀从下标 1 开始，不包含单词自身。被删除的词由一个更长的词覆盖；即使这个更长的词也被删除，沿后缀关系继续寻找，词长严格增加，最终一定到达某个保留词。因此删除后没有丢失任何编码需求。
剩余单词互不为后缀，将每个词写成
word + "#"再拼接，就能覆盖全部输入，长度为各个len(word) + 1之和。这个长度也是下界：若两个不同的保留词共用同一个结束分隔符，它们都是这段字符串的后缀，较短者必然是较长者的后缀，与保留条件矛盾。所以每个保留词都必须拥有不同的编码段，每段至少需要它的字符数加一个
#。上述拼接恰好达到下界，因而最短。
解题步骤
- 把所有单词加入集合，先消除重复单词。
- 遍历原数组，对每个词枚举起点
1..len(word)-1，从集合中删除对应后缀。- 删除时仍以原数组为枚举来源，不依赖集合当前保留了哪些词。
- 遍历最终集合，累加每个词的长度再加 1。长度为 1 的词没有真后缀，但仍可能作为更长词的后缀被删除。
代码实现
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
}
复杂度分析
设输入有
n个单词，最长词长为L。
- 时间复杂度：期望 $O(nL^2)$。每个词有 $O(L)$ 个后缀，哈希计算需要读取后缀字符，长度之和为 $O(L^2)$。Java 生成子串还会复制字符；Go 子串本身不复制字符，但哈希仍需扫描。
- 空间复杂度：不计输入字符串，Java 为 $O(n+L)$，Go 为 $O(n)$。集合最多保存
n个字符串引用或字符串头，Java 处理当前后缀另需至多 $O(L)$ 空间，Go 子串共享原字符串内容。
关键点总结
[!green]
- 能共用结束分隔符的是后缀关系，普通的子串或前缀关系不足以共享编码。
- 去重处理相同单词，删除真后缀处理不同长度单词之间的覆盖。
- 后缀关系具有传递性，被删除词最终仍由某个保留词覆盖。
- 保留词必须使用不同分隔符，长度求和同时给出了可行方案和最优下界。
易错点总结
[!yellow]
- 后缀起点必须从 1 开始，从 0 开始会把单词自身也删掉。
- 要检查所有真后缀，不能只删除最长的一个，也不能把前缀或任意子串当作可共享部分。
- 每个保留词都要加一个
#，包括最后一个词，不能只按词间分隔符计数。- 不先去重就求和，会为相同单词重复分配编码空间。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 208. 实现 Trie (前缀树) | 中等 | 把单词倒序插入Trie，使共同后缀转成共同前缀，最终只计没有被其他词包含的叶子。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！