友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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]仅由小写字母组成
思路分析
投机取巧的办法：给单词数组按照长度从大到小排列（长单词不可能为短单词的后缀），然后逐个判断已有助记词是否保护单词再决定是否添加。
更好的解法是：将单词反转，将单词添加到前缀树中，最后根据前缀树叶子简单对应的长度来计算结果。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-07-14 22:10:14
*/
public int minimumLengthEncoding(String[] words) {
// 按照长度从大到小排列，长度相同则按自然顺序排列
// 更长的单词不可能为别的单词的后缀
Arrays.sort(words, Comparator.comparing(String::length, Comparator.reverseOrder())
.thenComparing(Comparator.naturalOrder()));
StringBuilder sb = new StringBuilder();
for (String word : words) {
if (sb.indexOf(word + "#") >= 0) {
continue;
}
sb.append(word).append('#');
}
return sb.length();
}