示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文以 lcci/17.15.Longest Word/README_EN.md 为骨架结合仓库内 7 种语言的 Solution 实现完整讲解《程序员面试金典第 6 版》面试题 17.15 的题目语义、贪心排序与深度优先搜索组合的解题思路、复杂度推导与多语言实战代码。读完你将掌握一类「单词能否由字典中其他单词拼成」问题的标准解法并能在 Python、Java、C、Go、TypeScript、Rust、Swift 中自由迁移实现。题目背景与核心语义本题出自 LeetCode 面试题 17.15中文题解文档 同步收录于本仓库的lcci目录下属于《程序员面试金典第 6 版》第 17 章「重难」系列问题。题目要求给定一组单词words编写程序找出其中的最长单词且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果返回其中字典序最小的一项若没有符合要求的单词则返回空字符串。官方示例输入: [cat,banana,dog,nana,walk,walker,dogwalker] 输出: dogwalker 解释: dogwalker 可由 dog 和 walker 组成。数据范围题目给出的约束也是实现时必须满足的性能前提0 len(words) 100单词列表可为空1 len(words[i]) 100每个单词非空且长度不超过 100。这道题的核心难点并不在「能否拼接」本身而在两点一是拼接时单词允许重复使用如nana可由nana拼成前提是na也在词典中二是答案的择优规则先比长度、再比字典序。解法哈希表 排序 DFS正是针对这两点设计的。算法设计思路三个关键决策决策一用哈希表存储词典支持 O(1) 前缀查询把所有单词放入哈希集合s后续在 DFS 过程中需要反复判断「当前前缀是否是一个合法单词」哈希表的平均 O(1) 查找能把每次判断的成本降到最低。决策二先按长度降序、再按字典序升序排序实现「首个命中即答案」排序规则是整道题的择优核心长度降序保证先检查长的单词一旦命中即可提前返回无需继续处理较短候选长度相同时按字典序升序保证并列长度时字典序最小的单词最先被检查命中即为正确答案。仓库中 Python 实现 用一行排序表达了这个规则words.sort(keylambda x: (-len(x), x))先按-len(x)降序再按x本身升序字典序。决策三DFS 前先把自己从集合中移除杜绝「用自己拼自己」这是本解法最容易被忽略、却又至关重要的细节。遍历到单词w时先执行s.remove(w)Go 中为s[w] false再对w做 DFS 切分。原因很直观如果w本身还在集合里那么dfs第一次枚举前缀时就会命中w的完整前缀即w自身从而错误地返回true——相当于用「自己」拼出了「自己」违背了题目「由其他单词组合而成」的语义。DFS 判定流程详解对每个单词w定义递归函数dfs(w)其执行逻辑如下递归出口如果w为空字符串说明整段已经被完整切分成合法单词返回true枚举前缀遍历k 1到len(w)的所有前缀w[:k]若前缀w[:k]在哈希集合s中且对剩余部分w[k:]递归调用dfs返回true则整词可拼返回true兜底所有前缀均无法满足返回false。外层主流程遍历排序后的单词列表逐个移除自身并调用dfs第一个返回true的单词即为答案全部失败则返回空字符串。手工推演示例以dogwalker为例s中此时已移除dogwalker前缀枚举到k3dog命中集合 → 递归dfs(walker)dfs(walker)中枚举到k6walker命中集合 → 递归dfs()dfs()命中出口返回true逐层回溯最终dogwalker判定成功。注意到这个 DFS 本质上是「单词拆分word break」式的完全背包切分每一层只关心当前剩余串能否被切分成若干词典词。由于题目允许单词重复使用集合s在整个判定过程中不需要也不应该把已使用的前缀移除——这正是文档中特别强调的 each word can actually be reused 的体现。复杂度分析设n为单词列表长度、m为单词平均长度、M为最长单词长度时间复杂度O(m × n × log n n × 2^M)。其中排序开销为O(m × n × log n)每次比较需比较长度与字典序字典序比较最坏 O(m)对每个单词执行 DFS单个单词的切分状态数在最坏情况下达到2^M量级每个切分位置可取可不取共n个单词空间复杂度O(m × n)主要来自哈希集合存储全部单词以及 DFS 递归栈的深度开销。说明上述复杂度为题目文档与解法注释中给出的官方口径。在实际面试中还可以主动补充若单词间存在大量重叠前缀可引入记忆化memoization缓存dfs的中间结果将重复子问题的求解从指数级降到多项式级——这是该思路的自然延伸并非本题官方解法的必备部分。多语言实现仓库源码全览仓库为本题提供了 7 种语言的完整可运行实现代码与 README 中的解法一一对应可作为跨语言学习的对照样本。Python3class Solution: def longestWord(self, words: List[str]) - str: def dfs(w: str) - bool: if not w: return True for k in range(1, len(w) 1): if w[:k] in s and dfs(w[k:]): return True return False s set(words) words.sort(keylambda x: (-len(x), x)) for w in words: s.remove(w) if dfs(w): return w return 对应源码文件Solution.py。闭包捕获集合sdfs直接以切片递归代码最简。Javaclass Solution { private SetString s new HashSet(); public String longestWord(String[] words) { for (String w : words) { s.add(w); } Arrays.sort(words, (a, b) - { if (a.length() ! b.length()) { return b.length() - a.length(); } return a.compareTo(b); }); for (String w : words) { s.remove(w); if (dfs(w)) { return w; } } return ; } private boolean dfs(String w) { if (w.length() 0) { return true; } for (int k 1; k w.length(); k) { if (s.contains(w.substring(0, k)) dfs(w.substring(k))) { return true; } } return false; } }对应源码文件Solution.java。集合s作为类成员字段dfs通过substring枚举前缀排序用自定义比较器实现「长度降序 字典序升序」。Cclass Solution { public: string longestWord(vectorstring words) { unordered_setstring s(words.begin(), words.end()); ranges::sort(words, { return a.size() b.size() || (a.size() b.size() a b); }); auto dfs - bool { if (w.empty()) { return true; } for (int k 1; k w.size(); k) { if (s.contains(w.substr(0, k)) dfs(w.substr(k))) { return true; } } return false; }; for (const string w : words) { s.erase(w); if (dfs(w)) { return w; } } return ; } };对应源码文件Solution.cpp。采用 C20 特性ranges::sort进行范围排序、unordered_set::contains查询、递归 lambda 使用this auto dfs自引用语法注意这里递归传递的是string值每次切分产生新串。Gofunc longestWord(words []string) string { s : map[string]bool{} for _, w : range words { s[w] true } sort.Slice(words, func(i, j int) bool { return len(words[i]) len(words[j]) || (len(words[i]) len(words[j]) words[i] words[j]) }) var dfs func(string) bool dfs func(w string) bool { if len(w) 0 { return true } for k : 1; k len(w); k { if s[w[:k]] dfs(w[k:]) { return true } } return false } for _, w : range words { s[w] false if dfs(w) { return w } } return }对应源码文件Solution.go。Go 用map[string]bool充当集合移除自身时写s[w] false而非删除键dfs通过先声明再赋值的匿名函数实现递归。TypeScriptfunction longestWord(words: string[]): string { const s new Set(words); words.sort((a, b) (a.length b.length ? a.localeCompare(b) : b.length - a.length)); const dfs (w: string): boolean { if (w ) { return true; } for (let k 1; k w.length; k) { if (s.has(w.substring(0, k)) dfs(w.substring(k))) { return true; } } return false; }; for (const w of words) { s.delete(w); if (dfs(w)) { return w; } } return ; }对应源码文件Solution.ts。排序回调在长度相等时使用localeCompare做字典序比较语义与 Java 的compareTo对齐。Rustuse std::collections::HashSet; impl Solution { pub fn longest_word(words: VecString) - String { let mut s: HashSetString words.iter().cloned().collect(); let mut words words; words.sort_by(|a, b| b.len().cmp(a.len()).then(a.cmp(b))); fn dfs(w: String, s: mut HashSetString) - bool { if w.is_empty() { return true; } for k in 1..w.len() { if s.contains(w[0..k]) dfs(w[k..].to_string(), s) { return true; } } false } for w in words { s.remove(w); if dfs(w.clone(), mut s) { return w; } } String::new() } }对应源码文件Solution.rs。排序使用sort_by配合.then()链式比较先长度降序、再字典序升序dfs是带mut HashSet参数的独立函数切片w[0..k]借用后进行to_string递归。Swiftclass Solution { func longestWord(_ words: [String]) - String { var s: SetString Set(words) var words words words.sort { (a, b) - Bool in if a.count b.count { return a b } else { return a.count b.count } } func dfs(_ w: String) - Bool { if w.isEmpty { return true } for k in 1...w.count { let prefix String(w.prefix(k)) if s.contains(prefix) dfs(String(w.dropFirst(k))) { return true } } return false } for w in words { s.remove(w) if dfs(w) { return w } } return } }对应源码文件Solution.swift。Swift 的Set天然支持集合语义前缀用w.prefix(k)、剩余部分用w.dropFirst(k)表达。实现细节的跨语言对照与易错点语言集合容器移除自身长度/字典序排序前缀切分Pythonsets.remove(w)key(-len(x), x)切片w[:k]JavaHashSetStrings.remove(w)自定义比较器substring(0, k)Cunordered_setstrings.erase(w)lambda 比较器substr(0, k)Gomap[string]bools[w] falsesort.Slice回调切片w[:k]TypeScriptSetstrings.delete(w)localeComparesubstring(0, k)RustHashSetStrings.remove(w)sort_bythenw[0..k]SwiftSetStrings.remove(w)闭包比较w.prefix(k)面试与编码中需要重点警惕的易错点忘记在 DFS 前移除自身这是最常见的错误会导致所有单词包括不可由其他词拼成的都被误判为合法排序比较器的方向写反长度必须是降序b.length - a.length字典序必须是升序a.compareTo(b)二者方向相反极易混淆重复词的处理题目未禁止重复单词哈希集合天然去重不影响「由其他单词组合而成」的判定语义空列表边界当words为空时排序后循环体不执行直接返回符合题意。边界场景与解题启示无解场景列表[cat,dog]中没有任何词能由其他词拼成主循环全部dfs返回false最终返回空字符串单字母拼接场景[a,aa]中aa可由a a拼成——注意这依赖「单词允许重复使用」这一题目设定若题目改为「不可重复使用」则aa将不满足条件算法需要同步调整集合的增删策略并列择优场景[cat,dog,dogcat,catdog]中dogcat与catdog长度相同此时字典序更小的catdog应被选中排序规则保证了它会先于dogcat接受检查。从更大的视角看本题的「字典中单词能否由其他词拼成」是一个经典问题族它与力扣 139「单词拆分」同源后者只要求判断给定串能否拆分与力扣 472「连接词」几乎同题472 还要求收集全部连接词。掌握本题的「哈希集合 排序剪枝 DFS 前缀切分」三板斧后这些题目可以触类旁通。总结面试题 17.15 的官方解法脉络清晰哈希集合提供 O(1) 的词典查询双关键字排序把「最长 字典序最小」的择优转化为「首中即答案」的贪心DFS 完成单词拆分判定移出自身保证语义纯净。仓库在 README_EN.md 中给出完整推导并以 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.swift 七个独立文件落地了 7 种语言的实现是学习「一类组合词检测问题」的极佳对照样本。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐面试题 17.15「最长单词」详解哈希表 排序 DFS 组合拆词面试题 17.15「最长单词」详解哈希表 排序 DFS 组合拆词 《程序员面试金典第 6 版》面试题 17.15「最长单词」要求在给定单词列表中找示例工程教程InterviewGuide 哈希表专题LeetCode 720「词典中最长的单词」——排序 哈希集合判定前缀链InterviewGuide 哈希表专题LeetCode 720「词典中最长的单词」——排序 哈希集合判定前缀链 本篇技术指南围绕 InterviewGu文档教程知识库LeetCode 0049 字母异位词分组AlgoNote 哈希表 排序法题解LeetCode 0049 字母异位词分组AlgoNote 哈希表 排序法题解 给定一个字符串数组如何把「由相同字符重排而成」的字符串高效地归入同一组教程文档知识库创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
：用 TaoToken 统一 Key 跑通多工具代码生成链路)
