InterviewGuide 精选力扣 300+ 题解析：720. 词典中最长的单词（哈希表 + 排序前缀判定）

• 教程

本篇技术解析基于 InterviewGuide 仓库中 哈希表模块 的经典 Easy 题「720. 词典中最长的单词」（LeetCode：Longest Word in Dictionary）整理而成，完整代码收录于 720.词典中最长的单词.md。文章将带你吃透"逐步添加字母构词"的判定逻辑，掌握"排序 + 哈希集合"的高效解法，并深入理解其中一处决定成败的排序比较器设计技巧，这套思路在校招笔试与面试手写算法中非常实用。

题目描述

给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

换句话说，合法的候选单词w必须满足：w的所有前缀（去掉末尾一个字符后得到的字符串）都存在于词典中，并且这些前缀本身也是可以继续向前"剥壳"的，最终可以剥到一个长度为 1 的单词。因为词典中的单词全部由其他单词逐步添加一个字母而来，所以w的长度为 1、2、…、|w|-1的所有前缀都必须完整地出现在words中。

示例 1

输入: words = ["w","wo","wor","worl", "world"] 输出: "world" 解释: 单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。

"world"的前缀依次为"worl"、"wor"、"wo"、"w"，全部存在于词典中，因此合法；而它又是词典中最长的单词，所以直接作为答案返回。

示例 2

输入: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"] 输出: "apple" 解释: "apply"和"apple"都能由词典中的单词组成。但是"apple"的字典序小于"apply"。

这里出现了两个长度相同的候选单词"apply"和"apple"："apply"的前缀"appl"、"app"、"ap"、"a"都在词典中；"apple"同样满足。由于题目要求"返回字典序最小的单词"，因此答案是"apple"而非"apply"。至于"banana"，它的前缀"banan"等并不在词典中，直接出局。

约束条件

• 所有输入的字符串都只包含小写字母（共 26 个小写字母）；
• words数组长度范围为[1, 1000]；
• words[i]的长度范围为[1, 30]。

单词最大长度只有 30、数组最大长度 1000，因此即便是朴素的前缀枚举 + 集合查找也能在限定数据规模下高效运行，这正是本题能归入 Easy 等级的原因之一。

解题思路拆解

这道题的核心难点有三个：

1. 前缀链式判定：一个单词合法，要求它的全部前缀都出现在词典中，且这些前缀自身也要"逐层成立"。
2. 长度优先：在多个合法单词中，先取长度最长的。
3. 字典序兜底：长度相同的情况下，取字典序最小的。

一个很自然的想法是：先按长度从长到短考察，长度相同时按字典序从小到大考察，第一个找到的合法单词就是答案。实现时为了省去复杂的多层排序，可以反向思考——把单词按"长度升序、同长字典序降序"排序，然后从数组末尾往前遍历，此时最先遇到的合法单词恰好就是"最长且字典序最小"的候选。

第一版解法：排序 + 哈希集合（仓库收录解法）

仓库中收录的正是这一版解法，作者标注"看了提示，其实并没有什么窍门"，但代码中隐藏着一处非常关键的排序技巧。

bool compareSize(const string& a, const string& b) { if(a.size()!=b.size()) return a.size() < b.size(); else { return a > b;//当size一样时，字典序小的在后面，这一点很厉害 } } string longestWord(vector<string>& words) { sort(words.begin(), words.end(), compareSize); unordered_set<string> unst; for (auto& a : words) { unst.insert(a); } string result; for (int i=words.size()-1; i >=0;--i) {//从后往前走 result = words[i]; int len = result.size(); while (len--) { result.pop_back(); if (unst.find(result) == unst.end()) break; } if (len == 0) { result = words[i]; break; } } return result; }

比较器设计：一处"反直觉"的排序

if (a.size() != b.size()) return a.size() < b.size(); // 长度短的在前 else return a > b; // 长度相同时，字典序大的在前

乍看之下return a > b似乎写反了（正常应取字典序升序），但结合后面"从数组末尾往前遍历"的逻辑就豁然开朗了：

• 排序完成后，数组整体按长度升序排列；
• 长度相同的单词内部按字典序降序排列，于是同一长度内字典序最小的单词恰好排在最末尾；
• 从末尾倒序扫描时，先遇到的自然是"长度最长、且同长中字典序最小"的单词。

这样只需一次遍历就能同时满足"最长优先"和"字典序最小优先"两个目标，无需额外维护答案的优先级比较，是这段代码的精髓所在。

前缀链判定的执行细节

对于当前考察的单词result，用len记录其长度，然后进入while (len--)循环：

1. 每次循环先把len减 1，同时pop_back()去掉result的最后一个字符，得到去掉末尾后的前缀；
2. 在哈希集合unst中查找该前缀，若不存在则立即break，说明该单词不是合法候选；
3. 循环完全执行完毕后，len恰好自减为 0，此时说明单词的所有非空前缀（长度 1 到size-1）都已通过集合校验，该单词合法。

这里有个容易误读的细节：while (len--)是先判断len是否为 0 再进入循环体，循环内len已经先自减。假设单词长度为 5，则会依次检查长度为 4、3、2、1 的前缀，最后一次循环len从 1 自减为 0 时，result已经pop_back为空字符串，而空串必然不在词典中（单词长度下限为 1），于是必然break并得到len == 0。因此if (len == 0)成立，等价于"该单词的所有非空前缀都存在于词典中"，判定逻辑严密自洽。

找到第一个合法单词后立即break返回，因为它已经是"最长 + 字典序最小"的答案；若整个数组扫描完毕都没有合法单词，result维持初始值空字符串，恰好符合题目"无答案则返回空字符串"的要求。

复杂度分析

• 时间复杂度：排序最坏为 O(n·log n·L)（n 为单词个数，L 为单词平均长度，字符串比较本身需要 O(L)）；构建unordered_set为 O(n·L)；倒序遍历中每个单词最多被逐层剥壳 L 次，最坏 O(n·L)。整体在题目的数据规模（n ≤ 1000，L ≤ 30）下非常轻量。
• 空间复杂度：unordered_set存储全部单词，为 O(n·L)。

作者在该版本的提交记录中标注："执行用时 44 ms，在所有 C++ 提交中击败了 99.73% 的用户；内存消耗 16.2 MB，击败了 89.41% 的用户"。需要说明的是，这是当时提交环境下的历史数据，实际性能会随评测机与用例波动，核心价值在于算法思路本身。

边界情况与自测用例

为了保证解法正确，建议用以下几类用例自测：

• 无合法答案：words = ["a", "b", "c"]——没有任何单词能由其他单词逐步添加字母构成，应返回空字符串""；
• 单元素词典：words = ["a"]——"a"没有可依赖的前缀，同样返回""；
• 同长多候选：示例 2 中的["apply", "apple"]场景，验证字典序最小的"apple"被选中；
• 最长的单词并不合法：words = ["a", "aa", "ab", "aab"]——"aab"虽然最长，但前缀"ab"不在词典中，因此正确答案是"aa"（前缀"a"存在）。

延伸思考：能否用 Trie（前缀树）求解

本题的另一种经典思路是使用字典树 / 前缀树（Trie）：先把所有单词插入 Trie，然后从根节点出发做 DFS，每深入一层就在节点上记录"当前路径对应的单词是否完整出现在词典中"，只允许沿着"词尾节点"继续向下走，最终找到深度最大、且同深度下字典序最小的路径，即答案。该做法与本题"前缀链"语义天然契合，时间复杂度为 O(n·L)。

需要指出的是，当前 InterviewGuide 仓库的 LeetCode 题解集中暂未收录 Trie 解法的完整实现，哈希表分册下也以"哈希 + 排序 / 计数"为主，因此这里仅作为思路延伸，具体代码请结合你自己的 Trie 实现练习完成。

与仓库哈希表模块其他题解的呼应

本题在 哈希表 easy 汇总页 中与多道"字符串 + 哈希"题目并列，刷题时可串联对比，互为佐证：

• 884. 两句话中的不常见单词：用unordered_map做词频计数，与本题"前缀是否出现过"的集合判定形成"计数 vs 存在性"的对比；
• 648. 单词替换：同样围绕"前缀"展开，用unordered_set边累积字符边查前缀，是本题前缀判定思路的进阶应用；
• 692. 前 K 个高频单词：同样需要在"频率优先 + 字典序兜底"的双重排序下做选择，与本题"长度优先 + 字典序兜底"的排序哲学一脉相承，非常值得对照学习。

小结

"720. 词典中最长的单词"是一道把哈希集合查前缀与排序比较器技巧结合得恰到好处的经典题。仓库收录的解法用"长度升序 + 同长字典序降序"的排序，配合从尾部倒序扫描，一次遍历同时解决"最长优先"与"字典序最小"两个约束，while (len--)与空串必然查不到的特性又让前缀链判定写得极其精简。建议在理解上述推导后，脱离题解独立手写一遍，并尝试用 Trie 再实现一次，彻底掌握"前缀链类"题目的通用套路。

• 教程