企业官网建设流程全解析

LeetCode-Go 题解：720. Longest Word in Dictionary——排序 + 哈希表的贪心解法

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文讲解 LeetCode 第 720 题《Longest Word in Dictionary》（词典中最长的单词）在开源仓库 LeetCode-Go（README.md）中的完整题解。题目要求从给定字符串数组中找出"可以由其他单词逐步追加一个字母构造出来"的最长单词，若有多个答案则返回字典序最小的那个。读完本文你将掌握：如何用"先排序、再用哈希表逐层递推"的贪心思路在 O(n·L) 时间内解决问题，并能够对照仓库中的源码与测试用例（720. Longest Word in Dictionary.go）亲手验证算法正确性。

题目描述

Given a list of stringswordsrepresenting an English Dictionary, find the longest word inwordsthat can be built one character at a time by other words inwords. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

Input: words = ["w","wo","wor","worl", "world"] Output: "world" Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"] Output: "apple" Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Note:

• All the strings in the input will only contain lowercase letters.
• The length ofwordswill be in the range[1, 1000].
• The length ofwords[i]will be in the range[1, 30].

题目大意（中文题意）

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

解题思路：排序 + 哈希表贪心

原文档给出的核心思路非常精炼：先排序，排序完成以后就是字典序从小到大了；之后再用 map 辅助记录即可。下面结合仓库源码把这个思路展开讲透。

题目存在一个关键性质：一个单词能"由其他单词逐步添加一个字母组成"，当且仅当它的每一个前缀（去掉最后一个字符后）都存在于词典中。例如"world"可行，是因为"w"、"wo"、"wor"、"worl"全部在词典里。

这给出一个自然的递推关系：

• 长度为 1 的单词（单字母）天然可行，它是构造链的起点；
• 长度大于 1 的单词word可行，当且仅当word[:len(word)-1]（去掉末尾字符的前缀）可行。

利用这一递推关系，我们可以把"最长构造链"问题转化为一个线性扫描问题：

1. 先将所有单词按字典序排序（sort.Strings）；
2. 用一个map[string]bool记录"已经确认可行的单词"；
3. 遍历排序后的数组，对每个单词检查它是否可行：长度为 1，或它的前缀已在 map 中；
4. 可行则将其加入 map，并尝试更新最长答案（仅当更长时才更新）。

源码实现与逐行解读

仓库中的完整实现位于 720. Longest Word in Dictionary.go，源码如下：

package leetcode import ( "sort" ) func longestWord(words []string) string { sort.Strings(words) mp := make(map[string]bool) var res string for _, word := range words { size := len(word) if size == 1 || mp[word[:size-1]] { if size > len(res) { res = word } mp[word] = true } } return res }

逐行解读：

• sort.Strings(words)：按字典序升序排序整个数组。这一步是全局正确性的根基，它同时解决了两件事：
  1. 前缀先于完整词出现：在字典序下，"app"一定排在"apple"之前、"ap"一定排在"app"之前，因此扫描到某个单词时，它的所有前缀必然已经被处理过，map 中已经记录了它们是否可行；
  2. 同长度答案的字典序保证：相同长度的可行单词，字典序小的会先被扫描到。结合下面"仅当更长才更新"的规则，等长时较早出现（字典序更小）的答案不会被后来的单词覆盖。
• mp := make(map[string]bool)：哈希表，记录"可行的单词"。用bool作为 value，键存在即为true，因此mp[word[:size-1]]可以直接当布尔值使用——前缀不存在时，map 取零值false。
• size == 1 || mp[word[:size-1]]：核心判断。单字母单词直接可行；多字母单词要求其"去掉末尾字符"的前缀已经可行。
• if size > len(res)：用严格大于号更新答案。因为排序保证相同长度时字典序小的先出现，所以遇到更长单词才更新，等长时保留先出现的（即字典序更小的）结果。
• mp[word] = true：当前单词可行，标记入 map，供后续更长单词使用。
• 返回res：若没有任何可行单词，res保持空字符串，恰好满足题意"若无答案，则返回空字符串"。

核心细节：为什么这个贪心是正确的

1. 为什么排序后能保证"前缀先被处理"

字典序（lexicographical order）的定义保证了：若a是b的前缀（a = b[:len(a)]），则a一定排在b前面。因为按字典序比较时，b与a的前len(a)个字符完全相等，但b还有后续字符，故a < b。所以排序后从前向后扫描，每个单词的前缀必然已经完成判定并写入 map，mp[prefix]的查询结果是可信的。

这一点从测试用例也能看出：["a", "banana", "app", "appl", "ap", "apply", "apple"]排序后变为["a", "ap", "app", "appl", "apple", "apply", "banana"]，前缀关系被完整地整理成一条有序链。

2. 为什么只检查"去掉末尾一个字符"的前缀就够了

题目要求单词必须"一次添加一个字母"地构造，因此构造链上相邻两个词的长度恰好相差 1。只要word[:size-1]可行，就说明存在一条从单字母到该前缀的构造链，那么把前缀链继续追加一个字符即可得到word，构造链长度自动 +1。无需回溯检查更长的前缀——递推式已经保证了传递性。

3. 为什么用>而不是>=

排序后相同长度的单词按字典序排列。若用>=，等长的字典序较大的词会把字典序较小的词覆盖掉；而用严格>只允许"更长"的单词替换当前答案，从而在长度相同的候选之间保留最先出现（字典序最小）的那个。这正是"多个可行答案时返回字典序最小"题意的代码化表达。

4. 边界情况

• 数组中没有单字母单词：此时没有任何单词能满足size == 1 || mp[prefix]，map 始终为空，res保持""，返回空字符串，符合题意；
• 数组只有一个单词：若长度为 1 则返回它自身，否则返回空串；
• 所有单词都可构造（如示例 1）：返回最长的"world"。

复杂度分析

设n = len(words)，L为单词最大长度（题目约束L ≤ 30）：

• 时间复杂度：O(n·L·log n)。瓶颈在于sort.Strings的比较排序，字符串比较最坏为 O(L)；排序后的线性扫描为 O(n·L)（每次切片word[:size-1]与 map 查询均为 O(L) 级别）。总体可写作 O(n·L·log n)；
• 空间复杂度：O(n·L)。map 最多存放 n 个单词，每个单词长度不超过 L。

由于题目约束 n ≤ 1000、L ≤ 30，该解法在性能上完全游刃有余。

测试验证与运行方式

仓库为本题提供了配套测试 720. Longest Word in Dictionary_test.go，包含题目给出的两个官方示例：

package leetcode import ( "fmt" "testing" ) type question720 struct { para720 ans720 } // para 是参数 // one 代表第一个参数 type para720 struct { w []string } // ans 是答案 // one 代表第一个答案 type ans720 struct { one string } func Test_Problem720(t *testing.T) { qs := []question720{ { para720{[]string{"w", "wo", "wor", "worl", "world"}}, ans720{"world"}, }, { para720{[]string{"a", "banana", "app", "appl", "ap", "apply", "apple"}}, ans720{"apple"}, }, } fmt.Printf("------------------------Leetcode Problem 720------------------------\n") for _, q := range qs { _, p := q.ans720, q.para720 fmt.Printf("【input】:%v 【output】:%v\n", p, longestWord(p.w)) } fmt.Printf("\n\n\n") }

测试采用仓库统一的"表驱动（table-driven）"风格：para720定义入参、ans720定义期望答案，两个用例恰好覆盖了"最长唯一答案"与"等长取字典序最小"两种关键场景。在仓库根目录下运行：

go test -v ./leetcode/0720.Longest-Word-in-Dictionary/

即可看到测试输出与两个用例的input/output对照。

另外，仓库根目录的 gotest.sh 提供了全量测试脚本，通过go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...对全部 leetcode 目录下的题解生成统一的覆盖率文件，可作为批量验证的参考。项目要求 Go 1.19 及以上版本（见 go.mod）。

扩展：Trie 前缀树的另一条路

排序 + 哈希表的方案简洁直观，但并不是唯一解。本题的"前缀递推"语义天然契合Trie（前缀树/字典树）：将所有单词插入 Trie，再从根节点沿路径深度优先搜索，只有"完整单词节点"（对应单词存在于词典中）才能继续向下扩展，找出最深的完整路径即可。Trie 方案在需要保留所有前缀信息、或单词集合更大时优势更明显；而哈希表方案代码量更少、常数更小。本仓库采用哈希表方案，胜在思路清晰、易于理解与背诵。

总结

LeetCode 720 是一道典型的"贪心 + 哈希表"应用题，核心套路可以概括为三步：

1. 排序——让前缀天然先于完整词出现，同时顺便解决等长答案的字典序问题；
2. 哈希表记录可行前缀——以"去掉末尾字符的前缀可行"作为递推条件，把链式构造问题变成线性扫描；
3. 严格大于更新答案——保证多个最长答案中返回字典序最小者，无答案时自然返回空串。

这套"排序定序 + map 递推 + 贪心选优"的模式在字典类、前缀类问题中复用度极高，值得收录进自己的题解模板。对照 源码 与 测试用例 自行跑一遍，即可彻底掌握。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go