LeetCode 720. 词典中最长的单词

2022-10-11 HGNULB 约 11 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 720. 词典中最长的单词

题意分析

给定一个由小写字母单词组成的数组 words，要找出一个单词 w，使得 w 能够由 words 中的其它单词每次添加一个字母逐步拼出来。换句话说，w 的每一个真前缀（长度 $1$ 到 $ w -1$）都必须出现在 words 里。返回满足条件的最长单词；长度相同时返回字典序最小的；一个都没有则返回空串。

题面里的「每次添加一个字母」听起来像是一个构造过程，但它等价于一个纯粹的静态判定：只要 w 的所有真前缀都在词典中，那条从长度 1 逐步加到 |w| 的路径就自动存在。把动态构造改写成静态的前缀存在性检查，是这道题最关键的一次转译。

约束给了很强的信号：words.length ≤ 1000，words[i].length ≤ 30。总字符量不超过三万，所以完全允许对每个单词枚举它的全部前缀并逐个查询词典，不需要任何压缩或剪枝。反过来说，如果长度约束是 $10^5$ 级别，逐前缀取子串的做法就会退化，那时才需要考虑共享前缀的结构。

边界有三处值得先想清楚。第一，长度为 1 的单词没有真前缀，条件天然成立，它们是所有答案的起点。第二，答案不存在时要返回空串，而空串的长度为 0，恰好可以当作初始答案参与比较，不需要额外的「是否找到」标志。第三，比较规则是二级的：先比长度（长的赢），长度相等再比字典序（小的赢），两级顺序不能颠倒。

解法：哈希集合 + 前缀检查

核心思路

最直接的暴力是模拟题面：对每个单词，从长度 1 开始一层层往上找「上一个单词是否存在」，每次存在性判断都扫一遍整个数组。这样单次判断是 $O(n \cdot L)$，整体逼近 $O(n^2 L^2)$，瓶颈完全落在「某个字符串在不在词典里」这个反复出现的查询上。

瓶颈一旦定位，改法就明确了：把词典一次性装进一个支持 $O(1)$ 期望查询的容器，此后每次前缀查询都是常数级。这一步没有改变算法的结构，只是把重复的线性扫描换成了预处理后的直接查表。

于是判定规则可以显式地写出来。设 $S$ 是由 words 全部元素构成的集合，定义谓词 $ok(w)$ 为「对每个 $i \in [1, w -1]$，前缀 $w[0..i)$ 都属于 $S$」。$ok(w)$ 为真，当且仅当 w 可以被逐字母拼出。注意上界取 $ w -1$ 而不是 $ w $：w 自身当然在 $S$ 里，把它也检查一遍不会出错但毫无意义，而写成 i <= w.length() 更容易在别的题里引发混淆，这里统一按真前缀处理。

剩下的是挑选。维护一个 answer，初值为空串，遍历过程中对每个通过 ok 检查的 w 执行二级比较：|w| > |answer|，或者 |w| == |answer| 且 w 字典序更小时，更新 answer。空串作为初值同时承担了「还没找到答案」和「无解时的返回值」两个职责，因为任何非空单词都比它长，第一个合法单词必然会把它替换掉。

这里有一个容易被忽略的细节：谓词 ok 只依赖集合 $S$，而 $S$ 在整个挑选过程中是固定不变的。所以遍历 words 的顺序完全不影响结果，不需要事先排序。很多题解会先按「长度升序、字典序升序」排序然后返回第一个满足条件的单词，那是另一种等价写法，但排序本身是多余的开销。

解题步骤

第一步，把所有单词灌入集合 $S$。 为什么要先建完整个集合再开始检查：ok(w) 需要查询的前缀可能出现在 words 中 w 之后的位置，边建边查会漏掉这些后出现的前缀，导致本该合法的单词被判死。

第二步，遍历每个单词 w，调用 ok(w) 判定。 为什么不做任何长度过滤：过滤看似能剪枝（比如跳过比当前答案短的单词），但 ok 的检查次数本就受限于单词长度 $\le 30$，剪枝收益微乎其微，反而多一处出错的分支。

第三步，ok 内部从 i = 1 循环到 i < |w|，逐个取前缀查表。 为什么从 1 开始：i = 0 对应空串，空串不是词典元素，从 0 开始会让所有单词都被判死。为什么在 i = |w| 前停：那是单词自身，不属于真前缀。任一前缀缺失就立刻返回假，不必查完剩下的。

第四步，通过检查的单词参与二级比较更新答案。 为什么长度比较必须放在字典序前面：题目的首要目标是最长，只有在长度打平时字典序才成为决胜条件。两个条件写成 |w| > |answer| || (|w| == |answer| && w < answer) 的短路形式，正好实现这个优先级。

第五步，遍历结束返回 answer。 如果一个合法单词都没有，answer 保持初始的空串，正是题目要求的返回值。

以 words = ["a","banana","app","appl","ap","apply","apple"] 走一遍。先建集合 $S = {$a, banana, app, appl, ap, apply, apple$}$，answer = ""。

处理 a：长度为 1，ok 的循环一次都不进，直接返回真。比较 1 > 0，answer = "a"。

处理 banana：检查前缀 b，不在 $S$ 中，立刻返回假，跳过。注意这里只查了一次就退出，没有白白检查 ba、ban 等更长的前缀。

处理 app：检查 a（在）、ap（在），返回真。比较 3 > 1，answer = "app"。

处理 appl：检查 a、ap、app，全在，返回真。比较 4 > 3，answer = "appl"。

处理 ap：检查 a，在，返回真。但 2 > 4 不成立，2 == 4 也不成立，answer 保持 appl。这一步演示了「合法但不够长」的单词会被正确忽略。

处理 apply：检查 a、ap、app、appl，全在，返回真。5 > 4，answer = "apply"。

处理 apple：检查 a、ap、app、appl，全在，返回真。5 > 5 不成立，但 5 == 5 且 "apple" < "apply"（前四个字符 appl 完全相同，第五位 e 小于 y），所以 answer = "apple"。

遍历结束，返回 apple。整个过程中 apply 先于 apple 被处理，正是因为有了长度相等时的字典序比较，最终答案才没有停在 apply 上——这也说明为什么不能在找到第一个最长单词后就提前返回。

代码实现

class Solution {
    public String longestWord(String[] words) {
        Set<String> set = new HashSet<>();
        for (String w : words) {
            set.add(w);
        }

        String answer = "";
        for (String w : words) {
            if (!ok720(w, set)) {
                continue;
            }
            if (w.length() > answer.length() || (w.length() == answer.length() && w.compareTo(answer) < 0)) {
                answer = w;
            }
        }
        return answer;
    }

    private boolean ok720(String w, Set<String> set) {
        for (int i = 1; i < w.length(); i++) {
            if (!set.contains(w.substring(0, i))) {
                return false;
            }
        }
        return true;
    }
}

func longestWord(words []string) string {
    set := make(map[string]struct{}, len(words))
    for _, w := range words {
        set[w] = struct{}{}
    }

    answer := ""
    for _, w := range words {
        if !ok720(w, set) {
            continue
        }
        if len(w) > len(answer) || (len(w) == len(answer) && w < answer) {
            answer = w
        }
    }
    return answer
}

func ok720(w string, set map[string]struct{}) bool {
    for i := 1; i < len(w); i++ {
        if _, ok := set[w[:i]]; !ok {
            return false
        }
    }
    return true
}

复杂度分析

时间复杂度：$O(\sum w ^2)$。建集合是 $O(\sum w )$；每个单词要检查 $ w -1$ 个前缀，每个前缀的截取与哈希都是 $O( w )$ 量级，所以单个单词是 $O( w ^2)$。在 $n \le 1000$、$ w \le 30$ 的约束下，上界约为 $9 \times 10^5$ 次字符操作，远在可接受范围内。

空间复杂度：$O(\sum w )$。集合存下了全部单词的字符内容，这是唯一与输入规模相关的额外结构；Java 的 substring 会产生临时字符串，但它们生命周期极短，不改变数量级。

关键点总结

把过程性描述翻译成静态谓词。题面说「每次添加一个字母逐步构造」，实现上只需验证「所有真前缀都在集合中」。凡是遇到「逐步可达」类的描述，先问一句它是否等价于某个可以一次性验证的条件，往往能省掉一整套搜索。

重复的存在性查询就换容器。判断出瓶颈是「反复问某字符串在不在词典里」之后，剩下的只是选一个 $O(1)$ 查询的结构。这是一个可以无脑迁移的模式：先写暴力，定位到高频的成员查询，再用哈希把它压成常数。

用答案的自然初值消掉「是否找到」标志。空串长度为 0 且必然输给任何合法答案，于是它同时是哨兵和无解返回值。类似地，求最大值时用负无穷、求最小值时用正无穷，都是同一种技巧。

多级比较要按优先级短路。长度更大 || (长度相等 && 字典序更小) 这个形式把主次关系写进了表达式结构里，比先按一个维度筛再按另一个维度筛更不容易出错。

面试视角：这题真正的考点不在哈希集合，而在你能否说清「为什么不需要排序」和「什么时候必须换成字典树」。前者体现你看出了谓词与遍历顺序无关；后者体现你知道当单词很长、前缀高度共享时，逐前缀取子串的 $O( w ^2)$ 会变成瓶颈，此时按字典树自顶向下 DFS 可以做到总字符数级别。面试官若追问优化，先给出复杂度的具体来源，再给字典树方案，比一上来就写字典树更能展示分析能力。

别急着提前返回。找到第一个「最长」的单词并不意味着找到了答案，因为同长度里还可能有字典序更小的。凡是带 tie-break 的最值题，都必须走完整个遍历。

易错点总结

错误写法：前缀循环从 i = 0 开始。以 words = ["a"] 为例，i = 0 时取到空串，集合里没有空串，ok 返回假，a 被判死，最终返回空串而正确答案是 a。所有单词都会被这个 bug 判死，结果永远是空串。

错误写法：前缀循环写成 i <= w.length()。以 words = ["a","ap"] 为例，检查 ap 时最后一轮取到 ap 自身，虽然它在集合里所以碰巧不出错，但一旦改成用「先删除自身再查询」的变体实现，就会直接把每个单词都判死。这个越界写法在本题不暴露，在改写时才爆炸，属于埋雷型错误。

错误写法：只比较长度，忘记字典序 tie-break。以 words = ["a","ap","apply","appl","apple"] 为例，apply 先于 apple 出现并成为长度 5 的答案，之后 apple 因为「不比它长」被跳过，返回 apply，而正确答案是 apple。

错误写法：比较顺序写反成 w.compareTo(answer) < 0 || (相等长度 && 更长)。以 words = ["a","b","ba","bad"] 为例，a 字典序小于 bad，会把长度为 3 的正确答案 bad 覆盖成 a，返回 a。

错误写法：边遍历边把单词加入集合，省掉预处理循环。以 words = ["ap","a"] 为例，处理 ap 时集合里还没有 a，ap 被判死；处理 a 时通过，最终返回 a，而正确答案是 ap。输入顺序一变结果就变，是典型的「预处理没做完就开始查询」。

错误写法：找到第一个满足条件的最长单词后 return。以 words = ["a","ab","abc","ax","axy"] 为例，abc 先被找到并直接返回，但 axy 同为长度 3 且 abc < axy——这次碰巧对了；换成 words = ["a","ax","axy","ab","abc"]，就会返回 axy 而正确答案是 abc。

错误写法：Go 里用 len(w) > len(answer) 比较的同时，字典序用 strings.Compare(w, answer) > 0。以 words = ["a","ab","ac"] 为例，长度相等时会选中字典序更大的 ac，正确答案是 ab。Go 的字符串 < 已经是字典序比较，方向搞反是高频笔误。

错误写法：ok 中某个前缀缺失后不立即返回，而是置一个标志继续循环。以 words = ["banana"] 为例，本可以查一次 b 就退出，却要一直查到 banan，在长单词密集的输入下白白多出数倍字符操作；逻辑虽对，但在面试里会被追问为什么不短路。

错误写法：把 answer 初值设为 words[0]。以 words = ["banana"] 为例，banana 本身不合法（缺前缀 b），却被当作初始答案返回，正确答案是空串。

错误写法：用 w.length() >= answer.length() 一个条件代替二级比较。以 words = ["a","ab","ac"] 为例，ac 因为长度不小于 ab 而覆盖了它，返回 ac，正确答案是 ab。

相似题目

题目	难度	考察点
208. 实现 Trie (前缀树)	中等	手写字典树的插入与前缀查询，是本题在长单词场景下的替代结构
648. 单词替换	中等	同样查前缀，但要找的是最短匹配词根，且需要在句子中做替换
14. 最长公共前缀	简单	求所有单词共有的前缀，是纵向逐列比较而非查表判定
524. 通过删除字母匹配到字典里最长单词	中等	判定条件从「前缀」放宽为「子序列」，需双指针匹配，tie-break 规则与本题一致
820. 单词的压缩编码	中等	关注的是后缀包含关系，需反转字符串或用后缀字典树
211. 添加与搜索单词 - 数据结构设计	中等	查询串含通配符 `.`，纯哈希失效，必须借字典树做分支回溯
1160. 拼写单词	简单	判定依据是字符可用次数而非前缀结构，用计数数组而非集合
面试题 17.15. 最长单词	中等	单词可由其它单词拼接而成（不限于前缀链），需配合记忆化的可拆分判定