LeetCode 面试题 17.15. 最长单词
目录
题目描述
题意分析
给一组单词，找出其中最长的、可以由数组里其他单词拼接而成的单词；长度相同时取字典序最小的；一个都没有就返回空串。
「由其他单词拼成」有两层含义，都容易漏。一是材料可以重复使用，
"aa"可以由两个"a"拼出；二是不能把自己当作材料，否则每个单词都能「由自己拼成」，答案恒等于最长的那个词，题目就没意义了。「拼接」本身是一个熟悉的形状：判断一个串能否被切成若干段、每段都属于给定集合。它对每个候选词都是独立的一次判定，所以整体框架是「枚举候选词 × 判定一次」。
排除自身这件事，比看起来更值得设计。它不是判定过程里的一个特例，而是「判定时字典里放了什么」的问题——只要保证判定某个词时字典里没有它，就自动排除了自己，而且不用在切分逻辑里塞任何特判。
另外答案还有两级优先级：长度优先，长度相同比字典序。这提示我们可以让处理顺序与优先级顺序对齐，把比较逻辑压到最简。
边界：数组只有一个词时必然返回空串；某个词恰好等于另一个词加一个更短的词时也算合法；材料词自己是否可拆并不重要，只要它出现在数组里。
解法：排序 + 单词拆分 DP
核心思路
判定「一个词能否被字典拼出」的暴力写法是搜索：枚举第一段的长度，若这一段在字典里就递归判定剩下的部分。它会重复判定同一个后缀无数次，长度稍大就退化成指数级。
瓶颈很清楚：
"能否拼出前 i 个字符"这个问题被反复问到。把它记下来就是一维 dp。状态定义：对固定的单词word，dp[i]表示word的前i个字符能否由字典dict中的单词拼接而成。转移是枚举最后一段的起点j：只要存在j < i使得dp[j]为真且子串word[j..i)在字典里，dp[i]就为真。初值dp[0] = true，含义是空串可以由零个单词拼出；答案取dp[n]。剩下的问题是字典里该放哪些词。关键观察是：能拼出
word的材料一定严格比word短（至少两段，每段都非空）。所以只要把所有单词按长度升序排序，再依次处理，处理到word时把前面已处理的词放进字典，就同时得到两个性质——所有可能的材料都已经就位（不会漏判），而word自己还没进去（不会自拼）。等长的词也不会出问题：等长且不同的词无论如何拼不出word，因为拼接至少要两段、总长必然超出。于是不变量是：处理第
k个单词时，dict恰好等于前k-1个单词的集合，best是前k-1个单词里满足条件的最优答案。排序顺序还顺手解决了第三件事。等长时按字典序升序排，扫描顺序就与「长度最长、字典序最小」这个优先级完全对齐：更长的词一定后出现，等长中字典序小的先出现。所以更新答案时长度用严格大于即可，等长的后来者不会覆盖先来的。
解题步骤
- 排序：长度升序，等长时字典序升序：这一步是整个解法的地基，它同时保证了「材料先于成品」「自己不在字典里」和「答案优先级对齐」三件事。
- 准备
dict与best：dict用哈希集合，因为 dp 内层要做大量的子串存在性查询，必须是常数级；best初始化为空串，正好也是无解时的返回值。- 对每个词先判定、后加入：顺序绝对不能反。先
add再判定的话，任何词都能被自己「拼出」，答案会变成最长的那个词。- 判定内部跑一次拆分 dp：
dp[0] = true，外层i从 1 到n枚举前缀终点，内层j从 0 到i-1枚举最后一段的起点；dp[j]为假时直接跳过，因为不可达的切点不能作为后续拼接的落脚点。找到一个可行切分就break，dp[i]是布尔值，多找无益。- 字典为空时提前返回 false：这只是一个短路。即使不写，
dict为空时所有dp[i]（i ≥ 1）也都是 false，结果一样，省的是一趟无用循环。- 更新答案：可拆分且更长时替换
best；代码里还写了「等长且字典序更小」这一支，在当前排序下它永远不会被触发，留着是为了让「长度优先、字典序次之」的规则在代码里直接可读，也让这段逻辑在排序被改动时仍然正确。- 返回
best。以
["cat", "banana", "dog", "nana", "walk", "walker", "dogwalker"]走一遍。排序后的顺序是
cat(3)、dog(3)、nana(4)、walk(4)、banana(6)、walker(6)、dogwalker(9)——先按长度，等长的cat与dog、nana与walk、banana与walker各自按字典序排定。逐个处理：
cat：dict为空，直接判 false；dict = {cat}dog：子串"d"、"do"、"dog"都不在dict里，dp[1..3]全假，false；dict = {cat, dog}nana：任何前缀都不在dict里，dp[1]起就断了，false；dict = {cat, dog, nana}walk：同上，false；dict = {cat, dog, nana, walk}banana：dp[1]需要"b"、dp[2]需要"ba"，都不在字典里，第一刀就切不下去，后面的"nana"虽然在字典里但落脚点dp[2]为假，用不上，false；dict再加入bananawalker：dp[4]由dp[0]且"walk"在字典里而成立，但dp[6]需要"er"或"walker"在字典里，都没有，false；dict再加入walkerdogwalker：dp[3]由dp[0]且"dog"成立；dp[9]由dp[3]且"walker"成立，判定为真。它比当前best（空串）长，best = "dogwalker"返回
"dogwalker"。再看排序为什么不能省。如果一上来就把七个词全塞进
dict再逐个判定，那么处理cat时dp[3]会因为"cat"自己在字典里而成立，best立刻变成"cat"。换成输入["cat", "dog"]更明显：正确答案是空串，全塞进字典后会返回"cat"。
代码实现
class Solution {
// 先按长度升序处理，可以保证集合里都是不长于当前单词的候选词，拆分判断自然转成单词拆分问题。
public String longestWord(String[] words) {
Arrays.sort(
words,
(a, b) -> {
if (a.length() != b.length()) {
return Integer.compare(a.length(), b.length());
}
return a.compareTo(b);
});
Set<String> dict = new HashSet<>();
String best = "";
for (String word : words) {
if (wordBreak(word, dict)) {
if (word.length() > best.length()
|| (word.length() == best.length() && word.compareTo(best) < 0)) {
best = word;
}
}
dict.add(word);
}
return best;
}
private boolean wordBreak(String word, Set<String> dict) {
if (dict.isEmpty()) {
return false;
}
int n = word.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (!dp[j]) {
continue;
}
if (dict.contains(word.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}
func longestWord(words []string) string {
// 先按长度升序处理，可以保证集合里都是不长于当前单词的候选词，拆分判断自然转成单词拆分问题。
sort.Slice(words, func(i, j int) bool {
if len(words[i]) != len(words[j]) {
return len(words[i]) < len(words[j])
}
return words[i] < words[j]
})
dict := make(map[string]struct{})
best := ""
for _, word := range words {
if canBreak(word, dict) {
if len(word) > len(best) || (len(word) == len(best) && word < best) {
best = word
}
}
dict[word] = struct{}{}
}
return best
}
func canBreak(word string, dict map[string]struct{}) bool {
if len(dict) == 0 {
return false
}
n := len(word)
dp := make([]bool, n+1)
dp[0] = true
for i := 1; i <= n; i++ {
for j := 0; j < i; j++ {
if !dp[j] {
continue
}
if _, ok := dict[word[j:i]]; ok {
dp[i] = true
break
}
}
}
return dp[n]
}
复杂度分析
- 时间复杂度：$O(WL\log W + WL^3)$，其中 $W$ 是单词个数、$L$ 是最长单词的长度。排序做 $O(W\log W)$ 次比较、每次比较两个串是 $O(L)$；之后每个单词跑一次 dp，枚举 $O(L^2)$ 对
(i, j)，每对都要截取子串并求哈希，这一步是 $O(L)$。实际数据里 $L$ 很小，跑起来远达不到这个上界。- 空间复杂度：$O(WL)$，主要是哈希集合要存下所有单词的内容；每次 dp 只额外用一个长度 $L + 1$ 的布尔数组，用完即弃。
关键点总结
- 这题的内核就是单词拆分（139 题）加一个排序技巧。面试时一眼指出「这是 139 的变形，难点只在于怎么排除自身」，比现场从头推 dp 更能体现熟练度。
- 「不能用自己」应该通过控制字典的内容来解决——先判定、后加入——而不是在 dp 内部特判「整段就是自己」。前者顺带解决了材料就绪和优先级两个问题，后者遇到数组含重复词时还得再打补丁。
dp[0] = true表示空串可拼，是所有拆分型 dp 的起点；忘了它整张表全假。- 排序顺序、扫描顺序、答案优先级三者对齐，能把「长度最长、字典序最小」的比较逻辑压到几乎不用写。这种「让顺序替你做比较」的手法在很多题里都能复用。
- 内层必须先确认
dp[j]为真再查子串。不可达的切点如果也被采纳，等于承认了一个根本拼不出来的前缀。- 被追问优化时，标准答案是把哈希集合换成字典树：沿着树往下走一步就能同时判断所有以
j开头的子串是否成词，把每对(i, j)的 $O(L)$ 哈希开销降到均摊 $O(1)$。
易错点总结
- 把所有单词一次性放进字典再逐个判定：输入
["cat", "dog"]时"cat"被自己拼出，返回"cat"，正确答案是空串。- 先
dict.add(word)再判定：与上一条同样的后果，每个词都能自拼，最终返回最长的那个词。- 判定后忘记把
word加进字典：输入["cat", "dog", "catdog"]时字典始终为空，返回空串而不是"catdog"。- 只按长度排序、不排字典序，且更新时只比长度：输入
["a", "b", "ba", "ab"]时"ba"先被判定通过并占住best，返回"ba"，正确答案是"ab"。- 更新答案时用
>=比较长度：输入["a", "b", "ab", "ba"]时等长的后来者会覆盖先来的，同样返回"ba"。dp数组开成new boolean[n]或忘记dp[0] = true：所有词的dp全假，任何输入都返回空串。- 内层不检查
dp[j]就查子串：输入["cat", "dog", "zcatdog"]时，dp[4]会因为word[1..4) = "cat"在字典里而被置真，进而让dp[7]成立，返回"zcatdog"，可开头的z根本无处安放，正确答案是空串。- 用贪心代替 dp（每次匹配尽可能长的前缀）：字典是
{"ab", "abc", "cd"}而候选词是"abcd"时，贪心先吃掉"abc"，剩下"d"匹配失败就返回否，而"ab" + "cd"明明可行。- 以为材料只能用一次：输入
["a", "aa"]时正确答案是"aa"（两个"a"），限制不可重用会返回空串。- 对每个词跑不带记忆化的回溯：单词稍长就会把同一个后缀反复判定，指数级重复直接超时。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 139. 单词拆分 | 中等 | 本题内层 dp 的原型，字典由入参直接给出，不需要排除自身也不用排序 |
| 472. 连接词 | 困难 | 几乎同题，但要返回所有可被其他词拼出的单词，不做长度与字典序的择优 |
| 140. 单词拆分 II | 困难 | 从判定升级为枚举全部拆分方案，dp 要换成带记忆化的回溯并保存路径 |
| 720. 词典中最长的单词 | 中等 | 要求每个前缀都在词典里（逐字符生长），不是任意切分，判定条件更严 |
| 208. 实现 Trie (前缀树) | 中等 | 本题的优化方向，用它替换哈希集合可省掉每次子串截取与求哈希的开销 |