企业官网建设流程全解析

• 示例工程
• 教程

本文以 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"可由"na"+"na"拼成，前提是"na"也在词典中）；二是答案的择优规则（先比长度、再比字典序）。解法（哈希表 + 排序 + DFS）正是针对这两点设计的。

算法设计思路：三个关键决策

决策一：用哈希表存储词典，支持 O(1) 前缀查询

把所有单词放入哈希集合s，后续在 DFS 过程中需要反复判断「当前前缀是否是一个合法单词」，哈希表的平均 O(1) 查找能把每次判断的成本降到最低。

决策二：先按长度降序、再按字典序升序排序，实现「首个命中即答案」

排序规则是整道题的"择优核心"：

• 长度降序：保证先检查长的单词，一旦命中即可提前返回，无需继续处理较短候选；
• 长度相同时按字典序升序：保证并列长度时，字典序最小的单词最先被检查，命中即为正确答案。

仓库中 Python 实现 用一行排序表达了这个规则：

words.sort(key=lambda 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)，其执行逻辑如下：

1. 递归出口：如果w为空字符串，说明整段已经被完整切分成合法单词，返回true；
2. 枚举前缀：遍历k = 1到len(w)的所有前缀w[:k]：
   • 若前缀w[:k]在哈希集合s中，且对剩余部分w[k:]递归调用dfs返回true，则整词可拼，返回true；
3. 兜底：所有前缀均无法满足，返回false。

外层主流程：遍历排序后的单词列表，逐个移除自身并调用dfs，第一个返回true的单词即为答案；全部失败则返回空字符串""。

手工推演示例

以"dogwalker"为例（s中此时已移除"dogwalker"）：

• 前缀枚举到k=3，"dog"命中集合 → 递归dfs("walker")；
• dfs("walker")中枚举到k=6，"walker"命中集合 → 递归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 中的解法一一对应，可作为跨语言学习的对照样本。

Python3

class 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(key=lambda x: (-len(x), x)) for w in words: s.remove(w) if dfs(w): return w return ""

对应源码文件：Solution.py。闭包捕获集合s，dfs直接以切片递归，代码最简。

Java

class Solution { private Set<String> 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枚举前缀，排序用自定义比较器实现「长度降序 + 字典序升序」。

C++

class Solution { public: string longestWord(vector<string>& words) { unordered_set<string> 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。采用 C++20 特性：ranges::sort进行范围排序、unordered_set::contains查询、递归 lambda 使用this auto&& dfs自引用语法；注意这里递归传递的是string值，每次切分产生新串。

Go

func 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通过先声明再赋值的匿名函数实现递归。

TypeScript

function 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对齐。

Rust

use std::collections::HashSet; impl Solution { pub fn longest_word(words: Vec<String>) -> String { let mut s: HashSet<String> = 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 HashSet<String>) -> 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递归。

Swift

class Solution { func longestWord(_ words: [String]) -> String { var s: Set<String> = 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)表达。

实现细节的跨语言对照与易错点

面试与编码中需要重点警惕的易错点：

1. 忘记在 DFS 前移除自身：这是最常见的错误，会导致所有单词（包括不可由其他词拼成的）都被误判为合法；
2. 排序比较器的方向写反：长度必须是降序（b.length - a.length），字典序必须是升序（a.compareTo(b)），二者方向相反，极易混淆；
3. 重复词的处理：题目未禁止重复单词，哈希集合天然去重，不影响「由其他单词组合而成」的判定语义；
4. 空列表边界：当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 种语言的实现，是学习「一类组合词检测问题」的极佳对照样本。

• 示例工程
• 教程