最近在准备算法面试时发现 LeetCode 126 题“单词接龙II”是许多同学包括我自己的“拦路虎”。这道题不仅要求找到最短转换序列的长度还要输出所有可能的最短路径将 BFS 和 DFS 回溯结合对图论和搜索算法的理解要求很高。网上很多题解要么只讲思路要么代码不够清晰调试起来很费劲。本文将为你彻底拆解这道 Hard 题。我会从问题本质出发手把手带你用 Python 实现一个高效、清晰的解决方案。无论你是刚开始刷题的新手还是想优化现有解法的进阶者都能从本文获得一套可直接复用的“解题模板”并理解其背后的设计思想。我们将重点攻克如何构建隐式图、如何通过 BFS 进行层级遍历并记录路径关系、以及如何通过 DFS 回溯收集所有最短路径这三个核心难点。1. 问题理解与核心概念在开始写代码之前我们必须彻底理解题目在问什么以及它背后的数学模型。盲目动手只会事倍功半。1.1 题目描述与规则回顾LeetCode 126. 单词接龙 II 是经典“单词接龙”问题的升级版。给定一个起始单词beginWord、一个结束单词endWord和一个单词字典wordList。我们需要找出所有从beginWord到endWord的最短转换序列并返回这些序列列表。转换规则非常严格每次转换只能改变一个字母。转换过程中的每个中间单词都必须是字典wordList中的单词注意beginWord不一定在字典中但endWord必须在。如果没有这样的转换序列则返回空列表[]。示例 1输入beginWord “hit”, endWord “cog”, wordList [“hot”,”dot”,”dog”,”lot”,”log”,”cog”] 输出[[“hit”,”hot”,”dot”,”dog”,”cog”], [“hit”,”hot”,”lot”,”log”,”cog”]] 解释存在两种最短转换序列。示例 2输入beginWord “hit”, endWord “cog”, wordList [“hot”,”dot”,”dog”,”lot”,”log”] 输出[] 解释endWord“cog” 不在字典中所以无法完成转换。1.2 问题本质图的搜索这是理解本题的关键。我们可以将每个单词看作图中的一个节点。如果两个单词之间恰好只有一个字母不同那么它们之间就存在一条无向边。节点 (Node): 每个单词包括beginWord和wordList中的所有单词。边 (Edge): 连接两个仅有一个字母差异的单词。那么题目就转化为了一个经典的图论问题在无向图中找到从起点节点到终点节点的所有最短路径。这解释了为什么单纯的 BFS只能找一条最短路径不够用也解释了为什么我们需要记录节点的“父节点”关系来重建路径。1.3 单一路径 vs. 所有路径思路差异很多同学熟悉 LeetCode 127 题单词接龙它只要求返回最短路径的长度。其核心是一个标准的 BFS从起点开始 BFS。每层探索所有可能的下一跳单词。一旦遇到终点当前层数就是最短长度。对于 127 题我们通常使用一个visited集合来标记已访问的单词防止走回头路。但是对于 126 题这个策略行不通了。为什么考虑下图情况A - B (路径1) A - C - B (路径2)如果我们在第一次访问 B 时通过路径1就把它标记为visited那么路径2就无法到达 B 了我们会因此丢失一条有效的最短路径。因此对于“找出所有最短路径”的问题我们不能在第一次访问节点时就将其“关闭”。我们需要记录每个节点是在哪一层被首次发现的并且允许同层节点之间的访问。一个节点可以被多个上一层的节点访问即拥有多个“父节点”这正是多条路径产生的原因。2. 算法设计与核心思路理解了问题的图本质后我们设计一个两阶段算法BFS 建图 DFS 回溯收集。2.1 总体算法框架预处理与检查将wordList转为集合提高查找效率检查endWord是否存在。BFS 构建层级关系图从beginWord开始进行层级 BFS。目标记录每个节点是在哪一层被访问的distance以及每个节点的所有“父节点”parent。关键一个节点可以被同一层的不同节点访问但不能被更深层的节点再次访问否则路径会变长。当 BFS 到达endWord时并不立即停止而是完成当前层的遍历以确保找到所有在同一最短层级到达endWord的路径。DFS 回溯所有路径从endWord开始利用 BFS 阶段记录的parent关系向beginWord方向进行深度优先搜索。每找到一条完整的路径从endWord回溯到beginWord就将其反转并加入结果列表。2.2 数据结构选择word_set: 使用 Python 的set存储字典O(1)时间判断单词是否存在。queue: 使用collections.deque作为 BFS 队列。distance: 字典记录每个单词到起点的最短距离层级。distance[word] level。parent: 字典记录每个单词的所有前驱单词父节点。parent[word] [prev_word1, prev_word2, ...]。这是生成多条路径的核心。result: 列表存储所有最终的最短路径。2.3 单词变换的高效方法如何快速找到一个单词所有可能的“下一跳”最直观的方法是遍历字典逐个比较但时间复杂度为O(N*L)其中 N 是字典大小L 是单词长度在字典很大时效率低。更高效的方法是“虚拟节点”或“模式匹配”法 对于一个长度为 L 的单词例如 “hit”我们生成 L 种模式 “it”, “ht”, “hi*”。 所有能与 “hit” 相连的单词必然匹配其中一种模式例如 “hot” 匹配 “h*t”。因此我们可以预处理字典建立一个pattern_to_words的映射。但更常见的做法是在 BFS 过程中对当前单词的每个位置依次用a-z替换生成新单词并判断其是否在word_set中。虽然每次替换要尝试 26 次但总复杂度约为O(L * 26)通常比遍历整个字典要快。3. 环境准备与代码实现我们将使用 Python 3.8 进行实现。确保你的环境已就绪。本文代码不依赖任何第三方库。3.1 项目结构与依赖这是一个单文件的算法解题程序。你只需要一个 Python 解释器。# 文件word_ladder_ii.py # 描述LeetCode 126. 单词接龙 II 的 Python 解法3.2 完整代码实现下面是详细的、带有注释的代码实现。我们将按照算法框架分步构建最终的解。from collections import deque, defaultdict from typing import List class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) - List[List[str]]: 主函数寻找所有最短转换序列。 参数: beginWord: 起始单词 endWord: 目标单词 wordList: 单词字典列表 返回: 所有最短路径的列表每条路径是一个单词列表。 # 1. 预处理将wordList转为集合并检查endWord是否存在 word_set set(wordList) if endWord not in word_set: return [] # 目标单词不在字典中直接返回空列表 # 移除beginWord避免后续处理干扰如果它在字典中 word_set.discard(beginWord) # 2. 初始化数据结构 # distance 记录单词到起点的最短距离BFS层数 distance {beginWord: 0} # parent 记录每个单词的前驱单词列表用于回溯路径 parent defaultdict(list) # BFS队列 queue deque([beginWord]) found False # 标记是否找到endWord level 0 # 3. BFS 构建层级和父节点关系图 while queue and not found: level 1 # 当前层的大小用于分层处理 level_size len(queue) # 本层新访问的单词用于同一层内更新父节点关系 visited_this_level set() for _ in range(level_size): current_word queue.popleft() # 生成当前单词的所有可能下一跳 for next_word in self._get_next_words(current_word, word_set): # 情况1next_word 第一次被访问 if next_word not in distance: distance[next_word] level parent[next_word].append(current_word) queue.append(next_word) visited_this_level.add(next_word) if next_word endWord: found True # 找到但继续完成本层遍历 # 情况2next_word 在同一层被另一个当前单词访问到 # 这意味着存在另一条相同长度的路径到达 next_word elif distance[next_word] level: parent[next_word].append(current_word) # 情况3next_word 在更早的层被访问过忽略保证路径最短 # 关键步骤将本层访问过的单词从word_set中移除防止后续层再次访问 # 这保证了BFS的层级递增性也替代了visited集合的功能 word_set - visited_this_level # 4. DFS 回溯收集所有最短路径 result [] if found: # 只有找到终点才进行回溯 self._dfs_backtrack(endWord, beginWord, parent, [endWord], result) return result def _get_next_words(self, word: str, word_set: set) - List[str]: 辅助函数获取一个单词所有合法的下一跳单词。 通过替换每个位置的字母为a-z并检查是否在字典中来实现。 参数: word: 当前单词 word_set: 可用单词集合 返回: 合法下一跳单词的列表 next_words [] word_chars list(word) # 转为列表便于修改 for i in range(len(word_chars)): original_char word_chars[i] for c in abcdefghijklmnopqrstuvwxyz: if c original_char: continue # 跳过与原字母相同的情况 word_chars[i] c new_word .join(word_chars) if new_word in word_set: next_words.append(new_word) word_chars[i] original_char # 恢复原字符 return next_words def _dfs_backtrack(self, current_word: str, beginWord: str, parent: dict, path: List[str], result: List[List[str]]): 深度优先搜索回溯函数。 从终点(endWord)开始利用parent映射向起点(beginWord)回溯收集所有路径。 参数: current_word: 当前回溯到的单词 beginWord: 起始单词回溯终点 parent: 父节点关系字典 path: 当前回溯路径从终点到当前点 result: 存储最终结果的列表 if current_word beginWord: # 找到一条完整路径注意path是从终点到起点的需要反转 result.append(path[::-1]) return # 遍历当前单词的所有父节点前驱单词 for prev_word in parent[current_word]: path.append(prev_word) self._dfs_backtrack(prev_word, beginWord, parent, path, result) path.pop() # 回溯移除当前选择 # 用于本地测试的代码 if __name__ __main__: sol Solution() # 测试用例1 beginWord hit endWord cog wordList [hot,dot,dog,lot,log,cog] print(测试用例1:) print(fbeginWord: {beginWord}, endWord: {endWord}) print(fwordList: {wordList}) result sol.findLadders(beginWord, endWord, wordList) print(f所有最短路径: {result}) print(- * 40) # 测试用例2 beginWord hit endWord cog wordList [hot,dot,dog,lot,log] print(测试用例2:) print(fbeginWord: {beginWord}, endWord: {endWord}) print(fwordList: {wordList}) result sol.findLadders(beginWord, endWord, wordList) print(f所有最短路径: {result})3.3 代码分步解读与运行第一步预处理 (word_set)我们将wordList转换为集合使得判断单词是否存在的时间复杂度为 O(1)。同时检查endWord是否在集合中如果不在直接返回空列表这是一个重要的剪枝操作。第二步BFS 建图 (核心循环)这是算法最精妙的部分。我们使用queue进行层级遍历。distance字典记录每个节点被首次访问时的层级距离起点的步数。parent字典记录节点的所有前驱。这是生成多条路径的关键。我们分层处理 (level_size)这对于正确处理“同层节点互访”至关重要。对于当前单词current_word我们调用_get_next_words找到所有可能的下一跳。对于每个下一跳next_word首次访问记录距离设置父节点入队。同层再次访问仅更新父节点列表parent[next_word].append(current_word)不入队因为已经在本层被发现。更早层访问过忽略。这保证了我们找到的路径都是最短的。每层遍历结束后我们将本层新访问的所有单词从word_set中移除。这一步非常关键它确保了后续层的节点不会访问到本层及之前的节点防止路径变长。替代了传统的visited集合且允许同层节点互访。第三步DFS 回溯 (_dfs_backtrack)当 BFS 结束后如果找到了endWord(foundTrue)我们就从endWord开始利用parent关系进行深度优先搜索反向构建路径。path列表临时存储当前回溯路径从终点向起点。当回溯到beginWord时一条完整路径就产生了。由于path是反向的需要[::-1]反转后加入结果。通过递归遍历所有父节点我们就能枚举出所有最短路径。运行上述代码你会得到如下输出测试用例1: beginWord: hit, endWord: cog wordList: [hot, dot, dog, lot, log, cog] 所有最短路径: [[hit, hot, dot, dog, cog], [hit, hot, lot, log, cog]] ---------------------------------------- 测试用例2: beginWord: hit, endWord: cog wordList: [hot, dot, dog, lot, log] 所有最短路径: []输出与题目示例完全一致。4. 算法复杂度与优化分析理解算法的效率对于应对 LeetCode 的测试用例至关重要。4.1 时间复杂度分析设单词长度为 L字典单词数为 N。BFS 阶段最坏情况下每个单词都会被访问一次。对于每个单词生成其邻居需要 O(26*L) 的时间。因此BFS 的时间复杂度约为O(N * 26 * L)。由于 L 通常远小于 N且 26 是常数可以近似为O(N * L)。DFS 回溯阶段在最坏情况下图中可能存在指数级数量的最短路径例如一个完全二分图。因此DFS 的时间复杂度是O(P * L)其中 P 是路径总数每条路径长度约为最短路径长度 D。这是一个理论上的上界实际中由于单词接龙图的稀疏性通常不会达到。总时间复杂度O(NL PL)。对于主要考察 BFS 建图的部分我们关注 O(N*L)。4.2 空间复杂度分析word_set,distance,parent字典各需要 O(N) 的空间。BFS 队列最坏情况 O(N)。DFS 递归栈深度为最短路径长度 D需要 O(D) 的空间。结果列表result需要存储所有路径空间取决于路径数量和长度最坏情况是指数级。总空间复杂度O(N PD)其中 PD 是存储结果所需的空间。4.3 潜在优化点双向 BFS这是对标准 BFS 的一个著名优化。同时从beginWord和endWord开始进行 BFS。当两个搜索 frontier 相遇时就找到了最短路径。这可以显著减少搜索空间尤其是在分支因子较大的图中。实现双向 BFS 并记录父节点关系会稍微复杂一些但能提升性能。更高效的邻居查找如前所述可以使用“模式哈希”进行预处理。在算法开始前遍历wordList为每个单词的每种模式如 “ht”建立一个从模式到单词列表的映射。这样在 BFS 中找邻居时只需生成当前单词的模式并查表即可时间复杂度降为 O(L)。但预处理需要 O(NL) 的时间和空间。在字典很大时这是一个很好的权衡。提前终止在 BFS 中一旦我们处理完发现endWord的那一层就可以立即终止 BFS因为更深的层不可能产生更短的路径。我们的代码中found标志和继续完成当前层遍历的逻辑已经实现了这一点。5. 常见错误与排查指南在实现和调试这道题时以下几个坑点非常常见。5.1 错误类型与解决方案问题现象可能原因解决方案与排查思路输出结果缺失部分路径使用了简单的visited集合在第一次访问节点时就将其标记导致其他同层路径被截断。改用distance字典记录层级并允许同层访问。确保 BFS 是分层处理的并且parent记录了所有同层父节点。路径不是最短的BFS 过程中没有阻止深层节点访问浅层节点。例如第3层的节点访问了第1层的节点导致路径出现环或变长。在 BFS 访问邻居时如果邻居已被访问且其distance小于当前层必须跳过。同时每层结束后将已访问单词从word_set中移除是防止此问题的有效手段。递归深度超限或结果顺序不对DFS 回溯时如果从beginWord向endWord搜索由于分支多容易栈溢出且路径收集逻辑复杂。结果路径顺序反了。务必从endWord向beginWord回溯。因为parent关系是从子到父的反向回溯逻辑清晰天然形成路径。最后记得反转路径。endWord不在字典中时返回非空结果没有在算法开始前检查endWord是否在word_set中。在 BFS 开始前添加检查if endWord not in word_set: return []。beginWord在字典中导致干扰如果beginWord在wordList中它可能会被当作中间单词重复访问。在初始化word_set后执行word_set.discard(beginWord)。性能差超时使用List判断next_word in wordList时间复杂度为 O(N)。或者邻居生成效率低。1. 务必使用set。2. 检查邻居生成函数_get_next_words的实现确保是 O(26L) 而不是 O(NL)。考虑使用“模式哈希”预处理的优化。5.2 调试技巧打印关键变量在 BFS 循环中打印current_word,level,next_word,distance,parent的变化观察搜索过程。可视化小图用纸笔画出简单的单词接龙图例如3个字母的少量单词手动模拟算法的执行验证parent关系的构建是否正确。单元测试除了题目给的样例自己设计边界用例测试例如beginWord endWord。wordList为空。只有一条路径的情况。存在多条分支但最终汇聚到一点的情况。6. 最佳实践与工程化思考将一道算法题的解法学透并思考其工程应用才能获得最大收获。6.1 代码风格与可读性函数拆分如我们的代码所示将主逻辑 (findLadders)、邻居查找 (_get_next_words)、回溯 (_dfs_backtrack) 分离。这提高了代码的可读性和可测试性。有意义的变量名使用distance,parent,found而不是dist,par,flag。详细注释对复杂逻辑如 BFS 分层、同层访问处理、word_set的移除操作添加注释解释“为什么这么做”。类型提示使用 Python 的typing模块如List[str]可以提高代码的清晰度并得到 IDE 更好的支持。6.2 算法泛化与模板化本题的解法BFS建图DFS回溯是一个通用模式适用于在无权图中寻找所有最短路径的问题。你可以将其抽象为一个模板def find_all_shortest_paths_bfs_dfs(start, target, get_neighbors_func): 模板寻找图中两节点间所有最短路径。 start: 起点 target: 终点 get_neighbors_func: 函数输入一个节点返回其邻居节点列表 from collections import deque, defaultdict if target not in all_nodes: return [] distance {start: 0} parent defaultdict(list) queue deque([start]) found False level 0 while queue and not found: level 1 level_size len(queue) visited_this_level set() for _ in range(level_size): node queue.popleft() for neighbor in get_neighbors_func(node): if neighbor not in distance: distance[neighbor] level parent[neighbor].append(node) queue.append(neighbor) visited_this_level.add(neighbor) if neighbor target: found True elif distance[neighbor] level: parent[neighbor].append(node) # 根据具体问题决定是否移除已访问节点 # all_nodes - visited_this_level result [] if found: def backtrack(cur, path): if cur start: result.append(path[::-1]) return for prev in parent[cur]: path.append(prev) backtrack(prev, path) path.pop() backtrack(target, [target]) return result当遇到类似问题时你只需要实现特定的get_neighbors_func即可。6.3 扩展到实际场景“单词接龙”问题本身可以看作一种“状态空间搜索”。其思想可以应用到很多实际场景基因序列比对将基因序列视为单词单点突变视为一次转换寻找最短的突变路径。网络爬虫链接分析将网页视为节点链接视为边寻找网站间最短的导航路径。游戏求解如华容道将游戏盘面视为状态一次合法移动视为状态转换寻找最短解。理解 BFS 用于找最短步数并结合数据结构记录所有可能的前驱状态以回溯所有解是解决这类问题的核心技能。6.4 面试要点如果在面试中被问到这道题你可以按以下思路阐述问题转化首先说明这本质上是一个在无向图中找所有最短路径的问题。算法选择解释为什么单一 BFS 不够需要 BFS 记录层级和父关系再用 DFS 回溯。关键难点强调处理“同层节点互访”以找到所有路径以及如何避免路径变长通过distance和移除word_set。复杂度分析清晰说出时间空间复杂度并提及双向 BFS 等优化方向。代码实现写出结构清晰、有注释的代码。测试主动提出用不同的测试用例验证代码正确性。攻克 LeetCode 126 题“单词接龙II”是一次对图搜索算法的深度演练。它强迫我们超越简单的 BFS 模板去思考如何记录路径信息、如何处理多条最短路径、如何高效地构建和遍历隐式图。本文提供的解法在清晰度和效率之间取得了良好的平衡。记住核心使用 BFS 分层遍历并记录每个节点的所有父节点parent使用 DFS 从终点反向回溯收集路径。同时理解distance字典和word_set的移除操作对于保证路径最短和算法正确性至关重要。建议你亲自动手实现一遍代码并用不同的字典进行测试。尝试实现“双向 BFS”或“模式哈希”优化对比性能差异。当你真正理解了这个算法的每一个细节你不仅解决了一道 Hard 题更掌握了一套解决“所有最短路径”问题的强大工具。 LeetCode 126 单词接龙II：BFS建图与DFS回溯算法详解
最近在准备算法面试时发现 LeetCode 126 题“单词接龙II”是许多同学包括我自己的“拦路虎”。这道题不仅要求找到最短转换序列的长度还要输出所有可能的最短路径将 BFS 和 DFS 回溯结合对图论和搜索算法的理解要求很高。网上很多题解要么只讲思路要么代码不够清晰调试起来很费劲。本文将为你彻底拆解这道 Hard 题。我会从问题本质出发手把手带你用 Python 实现一个高效、清晰的解决方案。无论你是刚开始刷题的新手还是想优化现有解法的进阶者都能从本文获得一套可直接复用的“解题模板”并理解其背后的设计思想。我们将重点攻克如何构建隐式图、如何通过 BFS 进行层级遍历并记录路径关系、以及如何通过 DFS 回溯收集所有最短路径这三个核心难点。1. 问题理解与核心概念在开始写代码之前我们必须彻底理解题目在问什么以及它背后的数学模型。盲目动手只会事倍功半。1.1 题目描述与规则回顾LeetCode 126. 单词接龙 II 是经典“单词接龙”问题的升级版。给定一个起始单词beginWord、一个结束单词endWord和一个单词字典wordList。我们需要找出所有从beginWord到endWord的最短转换序列并返回这些序列列表。转换规则非常严格每次转换只能改变一个字母。转换过程中的每个中间单词都必须是字典wordList中的单词注意beginWord不一定在字典中但endWord必须在。如果没有这样的转换序列则返回空列表[]。示例 1输入beginWord “hit”, endWord “cog”, wordList [“hot”,”dot”,”dog”,”lot”,”log”,”cog”] 输出[[“hit”,”hot”,”dot”,”dog”,”cog”], [“hit”,”hot”,”lot”,”log”,”cog”]] 解释存在两种最短转换序列。示例 2输入beginWord “hit”, endWord “cog”, wordList [“hot”,”dot”,”dog”,”lot”,”log”] 输出[] 解释endWord“cog” 不在字典中所以无法完成转换。1.2 问题本质图的搜索这是理解本题的关键。我们可以将每个单词看作图中的一个节点。如果两个单词之间恰好只有一个字母不同那么它们之间就存在一条无向边。节点 (Node): 每个单词包括beginWord和wordList中的所有单词。边 (Edge): 连接两个仅有一个字母差异的单词。那么题目就转化为了一个经典的图论问题在无向图中找到从起点节点到终点节点的所有最短路径。这解释了为什么单纯的 BFS只能找一条最短路径不够用也解释了为什么我们需要记录节点的“父节点”关系来重建路径。1.3 单一路径 vs. 所有路径思路差异很多同学熟悉 LeetCode 127 题单词接龙它只要求返回最短路径的长度。其核心是一个标准的 BFS从起点开始 BFS。每层探索所有可能的下一跳单词。一旦遇到终点当前层数就是最短长度。对于 127 题我们通常使用一个visited集合来标记已访问的单词防止走回头路。但是对于 126 题这个策略行不通了。为什么考虑下图情况A - B (路径1) A - C - B (路径2)如果我们在第一次访问 B 时通过路径1就把它标记为visited那么路径2就无法到达 B 了我们会因此丢失一条有效的最短路径。因此对于“找出所有最短路径”的问题我们不能在第一次访问节点时就将其“关闭”。我们需要记录每个节点是在哪一层被首次发现的并且允许同层节点之间的访问。一个节点可以被多个上一层的节点访问即拥有多个“父节点”这正是多条路径产生的原因。2. 算法设计与核心思路理解了问题的图本质后我们设计一个两阶段算法BFS 建图 DFS 回溯收集。2.1 总体算法框架预处理与检查将wordList转为集合提高查找效率检查endWord是否存在。BFS 构建层级关系图从beginWord开始进行层级 BFS。目标记录每个节点是在哪一层被访问的distance以及每个节点的所有“父节点”parent。关键一个节点可以被同一层的不同节点访问但不能被更深层的节点再次访问否则路径会变长。当 BFS 到达endWord时并不立即停止而是完成当前层的遍历以确保找到所有在同一最短层级到达endWord的路径。DFS 回溯所有路径从endWord开始利用 BFS 阶段记录的parent关系向beginWord方向进行深度优先搜索。每找到一条完整的路径从endWord回溯到beginWord就将其反转并加入结果列表。2.2 数据结构选择word_set: 使用 Python 的set存储字典O(1)时间判断单词是否存在。queue: 使用collections.deque作为 BFS 队列。distance: 字典记录每个单词到起点的最短距离层级。distance[word] level。parent: 字典记录每个单词的所有前驱单词父节点。parent[word] [prev_word1, prev_word2, ...]。这是生成多条路径的核心。result: 列表存储所有最终的最短路径。2.3 单词变换的高效方法如何快速找到一个单词所有可能的“下一跳”最直观的方法是遍历字典逐个比较但时间复杂度为O(N*L)其中 N 是字典大小L 是单词长度在字典很大时效率低。更高效的方法是“虚拟节点”或“模式匹配”法 对于一个长度为 L 的单词例如 “hit”我们生成 L 种模式 “it”, “ht”, “hi*”。 所有能与 “hit” 相连的单词必然匹配其中一种模式例如 “hot” 匹配 “h*t”。因此我们可以预处理字典建立一个pattern_to_words的映射。但更常见的做法是在 BFS 过程中对当前单词的每个位置依次用a-z替换生成新单词并判断其是否在word_set中。虽然每次替换要尝试 26 次但总复杂度约为O(L * 26)通常比遍历整个字典要快。3. 环境准备与代码实现我们将使用 Python 3.8 进行实现。确保你的环境已就绪。本文代码不依赖任何第三方库。3.1 项目结构与依赖这是一个单文件的算法解题程序。你只需要一个 Python 解释器。# 文件word_ladder_ii.py # 描述LeetCode 126. 单词接龙 II 的 Python 解法3.2 完整代码实现下面是详细的、带有注释的代码实现。我们将按照算法框架分步构建最终的解。from collections import deque, defaultdict from typing import List class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) - List[List[str]]: 主函数寻找所有最短转换序列。 参数: beginWord: 起始单词 endWord: 目标单词 wordList: 单词字典列表 返回: 所有最短路径的列表每条路径是一个单词列表。 # 1. 预处理将wordList转为集合并检查endWord是否存在 word_set set(wordList) if endWord not in word_set: return [] # 目标单词不在字典中直接返回空列表 # 移除beginWord避免后续处理干扰如果它在字典中 word_set.discard(beginWord) # 2. 初始化数据结构 # distance 记录单词到起点的最短距离BFS层数 distance {beginWord: 0} # parent 记录每个单词的前驱单词列表用于回溯路径 parent defaultdict(list) # BFS队列 queue deque([beginWord]) found False # 标记是否找到endWord level 0 # 3. BFS 构建层级和父节点关系图 while queue and not found: level 1 # 当前层的大小用于分层处理 level_size len(queue) # 本层新访问的单词用于同一层内更新父节点关系 visited_this_level set() for _ in range(level_size): current_word queue.popleft() # 生成当前单词的所有可能下一跳 for next_word in self._get_next_words(current_word, word_set): # 情况1next_word 第一次被访问 if next_word not in distance: distance[next_word] level parent[next_word].append(current_word) queue.append(next_word) visited_this_level.add(next_word) if next_word endWord: found True # 找到但继续完成本层遍历 # 情况2next_word 在同一层被另一个当前单词访问到 # 这意味着存在另一条相同长度的路径到达 next_word elif distance[next_word] level: parent[next_word].append(current_word) # 情况3next_word 在更早的层被访问过忽略保证路径最短 # 关键步骤将本层访问过的单词从word_set中移除防止后续层再次访问 # 这保证了BFS的层级递增性也替代了visited集合的功能 word_set - visited_this_level # 4. DFS 回溯收集所有最短路径 result [] if found: # 只有找到终点才进行回溯 self._dfs_backtrack(endWord, beginWord, parent, [endWord], result) return result def _get_next_words(self, word: str, word_set: set) - List[str]: 辅助函数获取一个单词所有合法的下一跳单词。 通过替换每个位置的字母为a-z并检查是否在字典中来实现。 参数: word: 当前单词 word_set: 可用单词集合 返回: 合法下一跳单词的列表 next_words [] word_chars list(word) # 转为列表便于修改 for i in range(len(word_chars)): original_char word_chars[i] for c in abcdefghijklmnopqrstuvwxyz: if c original_char: continue # 跳过与原字母相同的情况 word_chars[i] c new_word .join(word_chars) if new_word in word_set: next_words.append(new_word) word_chars[i] original_char # 恢复原字符 return next_words def _dfs_backtrack(self, current_word: str, beginWord: str, parent: dict, path: List[str], result: List[List[str]]): 深度优先搜索回溯函数。 从终点(endWord)开始利用parent映射向起点(beginWord)回溯收集所有路径。 参数: current_word: 当前回溯到的单词 beginWord: 起始单词回溯终点 parent: 父节点关系字典 path: 当前回溯路径从终点到当前点 result: 存储最终结果的列表 if current_word beginWord: # 找到一条完整路径注意path是从终点到起点的需要反转 result.append(path[::-1]) return # 遍历当前单词的所有父节点前驱单词 for prev_word in parent[current_word]: path.append(prev_word) self._dfs_backtrack(prev_word, beginWord, parent, path, result) path.pop() # 回溯移除当前选择 # 用于本地测试的代码 if __name__ __main__: sol Solution() # 测试用例1 beginWord hit endWord cog wordList [hot,dot,dog,lot,log,cog] print(测试用例1:) print(fbeginWord: {beginWord}, endWord: {endWord}) print(fwordList: {wordList}) result sol.findLadders(beginWord, endWord, wordList) print(f所有最短路径: {result}) print(- * 40) # 测试用例2 beginWord hit endWord cog wordList [hot,dot,dog,lot,log] print(测试用例2:) print(fbeginWord: {beginWord}, endWord: {endWord}) print(fwordList: {wordList}) result sol.findLadders(beginWord, endWord, wordList) print(f所有最短路径: {result})3.3 代码分步解读与运行第一步预处理 (word_set)我们将wordList转换为集合使得判断单词是否存在的时间复杂度为 O(1)。同时检查endWord是否在集合中如果不在直接返回空列表这是一个重要的剪枝操作。第二步BFS 建图 (核心循环)这是算法最精妙的部分。我们使用queue进行层级遍历。distance字典记录每个节点被首次访问时的层级距离起点的步数。parent字典记录节点的所有前驱。这是生成多条路径的关键。我们分层处理 (level_size)这对于正确处理“同层节点互访”至关重要。对于当前单词current_word我们调用_get_next_words找到所有可能的下一跳。对于每个下一跳next_word首次访问记录距离设置父节点入队。同层再次访问仅更新父节点列表parent[next_word].append(current_word)不入队因为已经在本层被发现。更早层访问过忽略。这保证了我们找到的路径都是最短的。每层遍历结束后我们将本层新访问的所有单词从word_set中移除。这一步非常关键它确保了后续层的节点不会访问到本层及之前的节点防止路径变长。替代了传统的visited集合且允许同层节点互访。第三步DFS 回溯 (_dfs_backtrack)当 BFS 结束后如果找到了endWord(foundTrue)我们就从endWord开始利用parent关系进行深度优先搜索反向构建路径。path列表临时存储当前回溯路径从终点向起点。当回溯到beginWord时一条完整路径就产生了。由于path是反向的需要[::-1]反转后加入结果。通过递归遍历所有父节点我们就能枚举出所有最短路径。运行上述代码你会得到如下输出测试用例1: beginWord: hit, endWord: cog wordList: [hot, dot, dog, lot, log, cog] 所有最短路径: [[hit, hot, dot, dog, cog], [hit, hot, lot, log, cog]] ---------------------------------------- 测试用例2: beginWord: hit, endWord: cog wordList: [hot, dot, dog, lot, log] 所有最短路径: []输出与题目示例完全一致。4. 算法复杂度与优化分析理解算法的效率对于应对 LeetCode 的测试用例至关重要。4.1 时间复杂度分析设单词长度为 L字典单词数为 N。BFS 阶段最坏情况下每个单词都会被访问一次。对于每个单词生成其邻居需要 O(26*L) 的时间。因此BFS 的时间复杂度约为O(N * 26 * L)。由于 L 通常远小于 N且 26 是常数可以近似为O(N * L)。DFS 回溯阶段在最坏情况下图中可能存在指数级数量的最短路径例如一个完全二分图。因此DFS 的时间复杂度是O(P * L)其中 P 是路径总数每条路径长度约为最短路径长度 D。这是一个理论上的上界实际中由于单词接龙图的稀疏性通常不会达到。总时间复杂度O(NL PL)。对于主要考察 BFS 建图的部分我们关注 O(N*L)。4.2 空间复杂度分析word_set,distance,parent字典各需要 O(N) 的空间。BFS 队列最坏情况 O(N)。DFS 递归栈深度为最短路径长度 D需要 O(D) 的空间。结果列表result需要存储所有路径空间取决于路径数量和长度最坏情况是指数级。总空间复杂度O(N PD)其中 PD 是存储结果所需的空间。4.3 潜在优化点双向 BFS这是对标准 BFS 的一个著名优化。同时从beginWord和endWord开始进行 BFS。当两个搜索 frontier 相遇时就找到了最短路径。这可以显著减少搜索空间尤其是在分支因子较大的图中。实现双向 BFS 并记录父节点关系会稍微复杂一些但能提升性能。更高效的邻居查找如前所述可以使用“模式哈希”进行预处理。在算法开始前遍历wordList为每个单词的每种模式如 “ht”建立一个从模式到单词列表的映射。这样在 BFS 中找邻居时只需生成当前单词的模式并查表即可时间复杂度降为 O(L)。但预处理需要 O(NL) 的时间和空间。在字典很大时这是一个很好的权衡。提前终止在 BFS 中一旦我们处理完发现endWord的那一层就可以立即终止 BFS因为更深的层不可能产生更短的路径。我们的代码中found标志和继续完成当前层遍历的逻辑已经实现了这一点。5. 常见错误与排查指南在实现和调试这道题时以下几个坑点非常常见。5.1 错误类型与解决方案问题现象可能原因解决方案与排查思路输出结果缺失部分路径使用了简单的visited集合在第一次访问节点时就将其标记导致其他同层路径被截断。改用distance字典记录层级并允许同层访问。确保 BFS 是分层处理的并且parent记录了所有同层父节点。路径不是最短的BFS 过程中没有阻止深层节点访问浅层节点。例如第3层的节点访问了第1层的节点导致路径出现环或变长。在 BFS 访问邻居时如果邻居已被访问且其distance小于当前层必须跳过。同时每层结束后将已访问单词从word_set中移除是防止此问题的有效手段。递归深度超限或结果顺序不对DFS 回溯时如果从beginWord向endWord搜索由于分支多容易栈溢出且路径收集逻辑复杂。结果路径顺序反了。务必从endWord向beginWord回溯。因为parent关系是从子到父的反向回溯逻辑清晰天然形成路径。最后记得反转路径。endWord不在字典中时返回非空结果没有在算法开始前检查endWord是否在word_set中。在 BFS 开始前添加检查if endWord not in word_set: return []。beginWord在字典中导致干扰如果beginWord在wordList中它可能会被当作中间单词重复访问。在初始化word_set后执行word_set.discard(beginWord)。性能差超时使用List判断next_word in wordList时间复杂度为 O(N)。或者邻居生成效率低。1. 务必使用set。2. 检查邻居生成函数_get_next_words的实现确保是 O(26L) 而不是 O(NL)。考虑使用“模式哈希”预处理的优化。5.2 调试技巧打印关键变量在 BFS 循环中打印current_word,level,next_word,distance,parent的变化观察搜索过程。可视化小图用纸笔画出简单的单词接龙图例如3个字母的少量单词手动模拟算法的执行验证parent关系的构建是否正确。单元测试除了题目给的样例自己设计边界用例测试例如beginWord endWord。wordList为空。只有一条路径的情况。存在多条分支但最终汇聚到一点的情况。6. 最佳实践与工程化思考将一道算法题的解法学透并思考其工程应用才能获得最大收获。6.1 代码风格与可读性函数拆分如我们的代码所示将主逻辑 (findLadders)、邻居查找 (_get_next_words)、回溯 (_dfs_backtrack) 分离。这提高了代码的可读性和可测试性。有意义的变量名使用distance,parent,found而不是dist,par,flag。详细注释对复杂逻辑如 BFS 分层、同层访问处理、word_set的移除操作添加注释解释“为什么这么做”。类型提示使用 Python 的typing模块如List[str]可以提高代码的清晰度并得到 IDE 更好的支持。6.2 算法泛化与模板化本题的解法BFS建图DFS回溯是一个通用模式适用于在无权图中寻找所有最短路径的问题。你可以将其抽象为一个模板def find_all_shortest_paths_bfs_dfs(start, target, get_neighbors_func): 模板寻找图中两节点间所有最短路径。 start: 起点 target: 终点 get_neighbors_func: 函数输入一个节点返回其邻居节点列表 from collections import deque, defaultdict if target not in all_nodes: return [] distance {start: 0} parent defaultdict(list) queue deque([start]) found False level 0 while queue and not found: level 1 level_size len(queue) visited_this_level set() for _ in range(level_size): node queue.popleft() for neighbor in get_neighbors_func(node): if neighbor not in distance: distance[neighbor] level parent[neighbor].append(node) queue.append(neighbor) visited_this_level.add(neighbor) if neighbor target: found True elif distance[neighbor] level: parent[neighbor].append(node) # 根据具体问题决定是否移除已访问节点 # all_nodes - visited_this_level result [] if found: def backtrack(cur, path): if cur start: result.append(path[::-1]) return for prev in parent[cur]: path.append(prev) backtrack(prev, path) path.pop() backtrack(target, [target]) return result当遇到类似问题时你只需要实现特定的get_neighbors_func即可。6.3 扩展到实际场景“单词接龙”问题本身可以看作一种“状态空间搜索”。其思想可以应用到很多实际场景基因序列比对将基因序列视为单词单点突变视为一次转换寻找最短的突变路径。网络爬虫链接分析将网页视为节点链接视为边寻找网站间最短的导航路径。游戏求解如华容道将游戏盘面视为状态一次合法移动视为状态转换寻找最短解。理解 BFS 用于找最短步数并结合数据结构记录所有可能的前驱状态以回溯所有解是解决这类问题的核心技能。6.4 面试要点如果在面试中被问到这道题你可以按以下思路阐述问题转化首先说明这本质上是一个在无向图中找所有最短路径的问题。算法选择解释为什么单一 BFS 不够需要 BFS 记录层级和父关系再用 DFS 回溯。关键难点强调处理“同层节点互访”以找到所有路径以及如何避免路径变长通过distance和移除word_set。复杂度分析清晰说出时间空间复杂度并提及双向 BFS 等优化方向。代码实现写出结构清晰、有注释的代码。测试主动提出用不同的测试用例验证代码正确性。攻克 LeetCode 126 题“单词接龙II”是一次对图搜索算法的深度演练。它强迫我们超越简单的 BFS 模板去思考如何记录路径信息、如何处理多条最短路径、如何高效地构建和遍历隐式图。本文提供的解法在清晰度和效率之间取得了良好的平衡。记住核心使用 BFS 分层遍历并记录每个节点的所有父节点parent使用 DFS 从终点反向回溯收集路径。同时理解distance字典和word_set的移除操作对于保证路径最短和算法正确性至关重要。建议你亲自动手实现一遍代码并用不同的字典进行测试。尝试实现“双向 BFS”或“模式哈希”优化对比性能差异。当你真正理解了这个算法的每一个细节你不仅解决了一道 Hard 题更掌握了一套解决“所有最短路径”问题的强大工具。