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-GoREADME.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]去掉末尾字符的前缀可行。利用这一递推关系我们可以把最长构造链问题转化为一个线性扫描问题先将所有单词按字典序排序sort.Strings用一个map[string]bool记录已经确认可行的单词遍历排序后的数组对每个单词检查它是否可行长度为 1或它的前缀已在 map 中可行则将其加入 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)按字典序升序排序整个数组。这一步是全局正确性的根基它同时解决了两件事前缀先于完整词出现在字典序下app一定排在apple之前、ap一定排在app之前因此扫描到某个单词时它的所有前缀必然已经被处理过map 中已经记录了它们是否可行同长度答案的字典序保证相同长度的可行单词字典序小的会先被扫描到。结合下面仅当更长才更新的规则等长时较早出现字典序更小的答案不会被后来的单词覆盖。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。所以排序后从前向后扫描每个单词的前缀必然已经完成判定并写入 mapmp[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 -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对全部 leetcode 目录下的题解生成统一的覆盖率文件可作为批量验证的参考。项目要求 Go 1.19 及以上版本见 go.mod。扩展Trie 前缀树的另一条路排序 哈希表的方案简洁直观但并不是唯一解。本题的前缀递推语义天然契合Trie前缀树/字典树将所有单词插入 Trie再从根节点沿路径深度优先搜索只有完整单词节点对应单词存在于词典中才能继续向下扩展找出最深的完整路径即可。Trie 方案在需要保留所有前缀信息、或单词集合更大时优势更明显而哈希表方案代码量更少、常数更小。本仓库采用哈希表方案胜在思路清晰、易于理解与背诵。总结LeetCode 720 是一道典型的贪心 哈希表应用题核心套路可以概括为三步排序——让前缀天然先于完整词出现同时顺便解决等长答案的字典序问题哈希表记录可行前缀——以去掉末尾字符的前缀可行作为递推条件把链式构造问题变成线性扫描严格大于更新答案——保证多个最长答案中返回字典序最小者无答案时自然返回空串。这套排序定序 map 递推 贪心选优的模式在字典类、前缀类问题中复用度极高值得收录进自己的题解模板。对照 源码 与 测试用例 自行跑一遍即可彻底掌握。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解：720. Longest Word in Dictionary——排序 + 哈希表的贪心解法
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-GoREADME.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]去掉末尾字符的前缀可行。利用这一递推关系我们可以把最长构造链问题转化为一个线性扫描问题先将所有单词按字典序排序sort.Strings用一个map[string]bool记录已经确认可行的单词遍历排序后的数组对每个单词检查它是否可行长度为 1或它的前缀已在 map 中可行则将其加入 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)按字典序升序排序整个数组。这一步是全局正确性的根基它同时解决了两件事前缀先于完整词出现在字典序下app一定排在apple之前、ap一定排在app之前因此扫描到某个单词时它的所有前缀必然已经被处理过map 中已经记录了它们是否可行同长度答案的字典序保证相同长度的可行单词字典序小的会先被扫描到。结合下面仅当更长才更新的规则等长时较早出现字典序更小的答案不会被后来的单词覆盖。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。所以排序后从前向后扫描每个单词的前缀必然已经完成判定并写入 mapmp[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 -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对全部 leetcode 目录下的题解生成统一的覆盖率文件可作为批量验证的参考。项目要求 Go 1.19 及以上版本见 go.mod。扩展Trie 前缀树的另一条路排序 哈希表的方案简洁直观但并不是唯一解。本题的前缀递推语义天然契合Trie前缀树/字典树将所有单词插入 Trie再从根节点沿路径深度优先搜索只有完整单词节点对应单词存在于词典中才能继续向下扩展找出最深的完整路径即可。Trie 方案在需要保留所有前缀信息、或单词集合更大时优势更明显而哈希表方案代码量更少、常数更小。本仓库采用哈希表方案胜在思路清晰、易于理解与背诵。总结LeetCode 720 是一道典型的贪心 哈希表应用题核心套路可以概括为三步排序——让前缀天然先于完整词出现同时顺便解决等长答案的字典序问题哈希表记录可行前缀——以去掉末尾字符的前缀可行作为递推条件把链式构造问题变成线性扫描严格大于更新答案——保证多个最长答案中返回字典序最小者无答案时自然返回空串。这套排序定序 map 递推 贪心选优的模式在字典类、前缀类问题中复用度极高值得收录进自己的题解模板。对照 源码 与 测试用例 自行跑一遍即可彻底掌握。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考