教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载本篇技术解析基于 InterviewGuide 仓库中 哈希表模块 的经典 Easy 题「720. 词典中最长的单词」LeetCodeLongest 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和appleapply的前缀appl、app、ap、a都在词典中apple同样满足。由于题目要求返回字典序最小的单词因此答案是apple而非apply。至于banana它的前缀banan等并不在词典中直接出局。约束条件所有输入的字符串都只包含小写字母共 26 个小写字母words数组长度范围为[1, 1000]words[i]的长度范围为[1, 30]。单词最大长度只有 30、数组最大长度 1000因此即便是朴素的前缀枚举 集合查找也能在限定数据规模下高效运行这正是本题能归入 Easy 等级的原因之一。解题思路拆解这道题的核心难点有三个前缀链式判定一个单词合法要求它的全部前缀都出现在词典中且这些前缀自身也要逐层成立。长度优先在多个合法单词中先取长度最长的。字典序兜底长度相同的情况下取字典序最小的。一个很自然的想法是先按长度从长到短考察长度相同时按字典序从小到大考察第一个找到的合法单词就是答案。实现时为了省去复杂的多层排序可以反向思考——把单词按长度升序、同长字典序降序排序然后从数组末尾往前遍历此时最先遇到的合法单词恰好就是最长且字典序最小的候选。第一版解法排序 哈希集合仓库收录解法仓库中收录的正是这一版解法作者标注看了提示其实并没有什么窍门但代码中隐藏着一处非常关键的排序技巧。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(vectorstring words) { sort(words.begin(), words.end(), compareSize); unordered_setstring unst; for (auto a : words) { unst.insert(a); } string result; for (int iwords.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--)循环每次循环先把len减 1同时pop_back()去掉result的最后一个字符得到去掉末尾后的前缀在哈希集合unst中查找该前缀若不存在则立即break说明该单词不是合法候选循环完全执行完毕后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 ≤ 1000L ≤ 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 再实现一次彻底掌握前缀链类题目的通用套路。赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐InterviewGuide 哈希表专题LeetCode 720「词典中最长的单词」——排序 哈希集合判定前缀链InterviewGuide 哈希表专题LeetCode 720「词典中最长的单词」——排序 哈希集合判定前缀链 本篇技术指南围绕 InterviewGu文档教程知识库692. 前 K 个高频单词哈希表统计 堆/排序的 Top K 经典解法InterviewGuide 力扣刷题笔记692. 前 K 个高频单词哈希表统计 堆/排序的 Top K 经典解法InterviewGuide 力扣刷题笔记 本文是《InterviewGuid文档教程知识库LeetCode 720 词典中最长的单词哈希表模拟与字典树双解法实战解析LogicStack-LeetCode 题解精读LeetCode 720 词典中最长的单词哈希表模拟与字典树双解法实战解析LogicStack LeetCode 题解精读 本文是「宫水三叶的刷题日记」刷教程文档上一篇Stable Diffusion for BlenderDream Textures的未来演进与社区共建下一篇跨语言gRPC实战指南Go、Node.js、Java多场景开发解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考