这次我们来看 LeetCode 第 126 题“单词接龙 II”。这道题是“单词接龙 I”的进阶版不仅要求找到最短转换序列的长度还要找出所有可能的最短转换序列本身。它综合考察了图论BFS/DFS、字符串处理和回溯算法是面试中的高频难题。很多人在处理“找出所有路径”时容易超时或内存溢出本文将用 Python 带你拆解问题本质并提供一套清晰、高效且可复现的解决方案。核心挑战在于如何高效地构建单词间的转换关系图并利用广度优先搜索BFS找到最短路径的层级结构最后通过深度优先搜索DFS回溯出所有具体路径。盲目地进行 DFS 搜索会带来指数级的时间开销。本文将重点讲解双向 BFS 构建搜索树与DFS 回溯相结合的经典解法并分析其时间与空间复杂度。无论你是正在准备面试还是希望提升算法思维这套方法都能直接应用。本文将带你完成以下内容首先理解问题并分析难点然后详细拆解双向 BFS 构建邻接关系的步骤接着展示如何通过 DFS 回溯所有最短路径最后提供完整的 Python 代码实现、测试用例以及复杂度分析。我们重点关注算法的通用性和在不同规模输入下的表现。1. 核心能力速览在深入代码之前我们先通过一个表格快速了解本解法的核心特性和要求能力项说明问题类型图论搜索、回溯算法、字符串处理核心算法双向广度优先搜索 (Bidirectional BFS) 深度优先搜索 (DFS)时间复杂度O(N * L * 26 V E)其中 N 为单词表长度L 为单词长度。构建图占主导。空间复杂度O(N * L) 用于存储图结构和搜索过程中的队列、集合。关键优化点1. 使用双向 BFS 加速搜索并确定最短路径长度。2. 在 BFS 过程中记录每个单词的“父节点”关系构建出搜索树。3. 使用 DFS 在搜索树上回溯生成所有最短路径避免全图 DFS。输入/输出格式输入:beginWord(str),endWord(str),wordList(List[str])输出:List[List[str]]所有最短转换序列。适合场景面试算法准备、理解图搜索与回溯的结合、解决需要输出所有解的组合优化问题。不适合场景单词表极大如超过 5000且单词长度也很长时构建图的 O(NL26) 操作可能成为瓶颈需考虑更优的建图策略。2. 问题重述与难点分析题目要求 给定一个起始单词beginWord、一个结束单词endWord和一个单词列表wordList。需要找出从beginWord到endWord的所有最短转换序列。转换规则如下每次转换只能改变一个字母。转换过程中的每个中间单词必须是wordList中的单词beginWord不需要在列表中但endWord必须在。示例输入 beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log,cog] 输出 [ [hit,hot,dot,dog,cog], [hit,hot,lot,log,cog] ]难点分析找出所有路径而非一条这是与第 127 题单词接龙 I的本质区别。简单的 BFS 只能找到一条路径或最短长度无法记录所有分支。避免指数级搜索最朴素的想法是从起点开始 DFS但单词表构成一张图DFS 可能会探索所有可能的路径时间复杂度过高。确定搜索边界我们需要知道最短路径的长度是多少才能在这个边界内进行有效搜索避免搜索过深。高效构建邻居关系如何快速判断两个单词是否只差一个字母直接两两比较是 O(N² * L)对于较大的 N 不可接受。解决方案思路 采用双向 BFS 构建搜索树 DFS 回溯的策略。阶段一双向 BFS从起点和终点同时开始进行层级扩散的 BFS。当两边搜索相遇时我们就确定了最短路径长度并且在搜索过程中我们会记录每个单词是从哪些“父单词”扩展而来的。这形成了一棵或多棵反向的搜索树树根是endWord。阶段二DFS 回溯从endWord出发沿着阶段一记录的“父节点”关系反向 DFS 回溯到beginWord即可构造出所有从起点到终点的最短路径。这个方法的关键在于BFS 保证了我们找到的是最短路径层级而记录的父子关系为我们后续 DFS 提供了精确的、不会绕远路的搜索空间。3. 环境准备与算法依赖本算法实现不依赖特定的第三方库只需要标准的 Python 环境。但为了更好的开发体验建议进行如下准备Python 环境推荐 Python 3.8 及以上版本。可以在终端使用python --version检查。代码编辑器/IDEVS Code, PyCharm, Jupyter Notebook 等均可。理解基础数据结构算法中会频繁使用set集合、dict字典、deque双端队列、list列表和defaultdict默认字典。确保你了解它们的时间复杂度。set: 用于 O(1) 时间判断成员是否存在。dict/defaultdict: 用于存储图结构和父子关系。deque: 用于 BFS 队列提供高效的 popleft 操作。算法前置知识广度优先搜索 (BFS)层级遍历思想。深度优先搜索 (DFS)递归或栈实现回溯。图的表示邻接表。在本问题中我们不会显式构建完整的图而是动态生成邻居。核心数据结构设计wordSet: 将wordList转为集合用于 O(1) 的查找。parents: 一个字典键为单词值为一个集合存储该单词的所有“父节点”即在 BFS 中能一步转换到该单词的那些单词。这个结构是构建搜索树的关键。queue: BFS 使用的队列。visited: 记录在当前层级已访问过的单词避免重复访问同一层级注意不同路径在同一层级访问同一单词是允许的这是找到所有路径的关键。4. 算法步骤详细拆解4.1 步骤一预处理与初始化首先进行边界条件检查和数据准备。将wordList转换为集合wordSet提高查找效率。检查endWord是否在wordSet中如果不在直接返回空列表[]因为不可能到达。初始化数据结构queue collections.deque([beginWord])单向 BFS 初始化双向 BFS 稍复杂visited set([beginWord])记录已访问节点。parents collections.defaultdict(set)记录父子关系。found False标记是否已找到最短路径。level 0当前 BFS 的层级。为了支持双向 BFS我们还需要一个从终点开始的队列和访问集合但更常见的实现是使用一个队列但在每层循环中交替处理“当前层所有节点”。为了清晰我们先讲解单向 BFS 记录父子关系的原理再扩展到双向 BFS。4.2 步骤二单向 BFS 构建父子关系树原理在标准的层级 BFS 中我们遍历当前队列中的所有单词即同一层的单词对于每个单词生成其所有可能的“下一个单词”即改变一个字母且在wordSet中的单词。如果这个“下一个单词”没有被访问过则将其加入队列和已访问集合并记录父子关系parents[next_word].add(current_word)。如果这个“下一个单词”已经被访问过但访问它的层级与当前层级相同即它是在本层由其他单词扩展出来的那么我们仍然需要记录这个新的父子关系因为这是另一条最短路径。这是实现“记录所有最短路径”的关键。如果“下一个单词”是endWord我们标记found True。注意此时不要立即停止需要完成当前层的所有遍历以确保收集到本层所有能到达endWord的路径。当一层遍历结束后如果found为True则 BFS 结束。此时parents字典中就存储了从beginWord到endWord最短路径上的所有父子关系。生成邻居的优化技巧 对于单词word逐个位置尝试将其替换为 ‘a’ 到 ‘z’ 的 26 个字母生成新单词new_word判断new_word是否在wordSet中。时间复杂度为 O(26 * L)其中 L 为单词长度。这比两两比较单词 (O(N²)) 高效得多。4.3 步骤三双向 BFS 优化单向 BFS 从起点扩散直到遇到终点。搜索空间近似为一个球形。双向 BFS 同时从起点和终点扩散当两个搜索球相遇时停止可以显著减少搜索的节点数尤其当分支因子较大时。实现细节我们使用两个集合begin_queue和end_queue实际用set表示当前层节点更方便以及begin_visited和end_visited字典记录单词和其对应的层级。每次迭代选择节点数较少的那一端进行扩展平衡两端搜索速度。在扩展某一端的当前层时对于每个单词生成邻居。如果生成的邻居在另一端的已访问集合中说明两端相遇最短路径找到。在扩展过程中同样需要记录父子关系。为了后续 DFS 回溯方便我们通常固定从终点向起点回溯。因此在 BFS 过程中我们始终记录parents[child_word] parent_word并且 BFS 的方向是从起点向终点或者通过一些技巧保证parents关系的方向一致。为了简化理解和代码实现许多成功的解法采用了一次 BFS从起点开始来构建parents关系图因为这对于找出所有最短路径已经足够。双向 BFS 主要用于快速确定最短路径长度和减少构建parents图时的搜索空间。下面的代码实现将展示结合了双向 BFS 思想来加速搜索的版本。4.4 步骤四DFS 回溯所有路径BFS 结束后我们得到了parents图和found标志。如果found为True我们就可以进行 DFS 回溯。起点endWord终点beginWord路径我们从endWord开始将其加入当前路径。递归过程对于当前单词current在parents[current]中找到它的所有父单词。对每个父单词递归调用 DFS。终止条件当current beginWord时说明我们已经回溯到了起点。此时当前路径是一条从endWord到beginWord的逆序路径。我们需要将其反转然后加入到最终结果列表中。由于parents图是在 BFS 按层级构建的它保证了回溯出的任何路径长度都是最短的。5. 完整 Python 代码实现与注释以下是结合了双向 BFS 优化和 DFS 回溯的完整代码实现。代码包含了详细的注释帮助你理解每一步。from collections import defaultdict, deque from typing import List class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) - List[List[str]]: # 步骤1: 预处理将wordList转为集合并检查endWord是否存在 wordSet set(wordList) if endWord not in wordSet: return [] # 移除beginWord避免后续处理中的干扰如果它在列表中 wordSet.discard(beginWord) # 步骤2: 初始化数据结构 # parents 记录每个单词的父节点集合哪些单词可以一步转换到它 parents defaultdict(set) # 使用双向BFS初始化两个队列和已访问字典记录单词和其所在层级 begin_queue {beginWord} end_queue {endWord} begin_visited {beginWord: 0} # 单词层级 end_visited {endWord: 0} found False reverse False # 方向标志False表示从begin向end扩展True表示从end向begin扩展 depth 0 # 步骤3: 双向BFS构建parents图 while begin_queue and not found: depth 1 next_level set() # 遍历当前层的所有单词 for current_word in begin_queue: # 生成当前单词的所有可能邻居 for i in range(len(current_word)): for c in abcdefghijklmnopqrstuvwxyz: if c current_word[i]: continue next_word current_word[:i] c current_word[i1:] # 关键逻辑开始 if next_word in wordSet or next_word in end_visited: # 如果next_word在另一端已被访问说明相遇 if next_word in end_visited: found True # 记录父子关系。注意方向我们希望parents[child] parent # 当前搜索方向是 begin - end所以 current_word 是 parent, next_word 是 child # 但如果reverse为True说明当前是从end向begin搜索关系要反过来 if not reverse: parents[next_word].add(current_word) else: parents[current_word].add(next_word) # 如果next_word未被本端访问过则加入下一层 if next_word not in begin_visited: begin_visited[next_word] depth next_level.add(next_word) # 准备下一层 begin_queue next_level # 交换两端队列和访问字典实现交替扩展总是扩展较小的一端 if len(begin_queue) len(end_queue): begin_queue, end_queue end_queue, begin_queue begin_visited, end_visited end_visited, begin_visited reverse not reverse # 交换方向时方向标志取反 # 步骤4: 如果未找到路径返回空列表 if not found: return [] # 步骤5: DFS回溯收集所有最短路径 results [] def dfs_backtrack(node: str, path: List[str]): 从当前节点node回溯到beginWord if node beginWord: # 找到一条完整路径当前path是从endWord到beginWord的逆序 results.append(path[::-1]) # 反转路径并加入结果 return # 遍历当前节点的所有父节点 for parent in parents[node]: path.append(parent) dfs_backtrack(parent, path) path.pop() # 回溯 # 从endWord开始回溯 dfs_backtrack(endWord, [endWord]) return results # 测试代码 if __name__ __main__: solution Solution() # 测试用例1: 题目示例 beginWord hit endWord cog wordList [hot,dot,dog,lot,log,cog] print(测试用例1:) print(f输入: beginWord{beginWord}, endWord{endWord}, wordList{wordList}) result solution.findLadders(beginWord, endWord, wordList) print(f输出: {result}) print(预期: [[hit,hot,dot,dog,cog], [hit,hot,lot,log,cog]]) print() # 测试用例2: 无解情况 beginWord hit endWord cog wordList [hot,dot,dog,lot,log] # 缺少cog print(测试用例2 (无解):) print(f输入: beginWord{beginWord}, endWord{endWord}, wordList{wordList}) result solution.findLadders(beginWord, endWord, wordList) print(f输出: {result}) print(预期: []) print() # 测试用例3: 更复杂的例子 beginWord red endWord tax wordList [ted,tex,red,tax,tad,den,rex,pee] print(测试用例3:) print(f输入: beginWord{beginWord}, endWord{endWord}, wordList{wordList}) result solution.findLadders(beginWord, endWord, wordList) print(f输出: {result}) # 预期路径之一: [red,ted,tad,tax] # 预期路径之二: [red,ted,tex,tax] # 预期路径之三: [red,rex,tex,tax] print(f找到 {len(result)} 条路径。) for path in result: print(f {path})6. 代码逐段解析与关键点6.1 数据结构初始化wordSet set(wordList) if endWord not in wordSet: return [] wordSet.discard(beginWord)使用set是为了 O(1) 的查找时间复杂度这是性能的基础。提前检查endWord可避免无谓的搜索。discard移除beginWord防止它干扰邻居生成因为它可能不在原始列表中也可能在。6.2 双向 BFS 循环逻辑while begin_queue and not found: depth 1 next_level set() for current_word in begin_queue: # ... 生成邻居并处理 ... begin_queue next_level # 交换两端队列总是扩展较小的一端begin_queue和end_queue使用set而不是deque因为在这一层我们只需要遍历集合中的所有元素而不关心顺序。set还能自动去重。next_level也是一个set用于收集下一层要扩展的单词。交换队列这是一个重要优化。每次扩展后比较两端待扩展集合的大小选择较小的那个进行下一轮扩展这有助于平衡搜索尽快相遇。6.3 邻居生成与父子关系记录for i in range(len(current_word)): for c in abcdefghijklmnopqrstuvwxyz: if c current_word[i]: continue next_word current_word[:i] c current_word[i1:] if next_word in wordSet or next_word in end_visited: # ... 判断相遇和记录关系 ...邻居生成复杂度为 O(26*L)对于 L5 的单词最多生成 130 个候选比比较整个单词表高效。if next_word in wordSet or next_word in end_visited:这个条件很关键。wordSet是合法单词库end_visited包含了另一端已访问的单词即使它可能不在原始wordList中比如beginWord。这保证了搜索的正确性。父子关系方向reverse标志位确保了无论从哪一端扩展parents[child]中存储的始终是parent即parent - child是搜索进行的方向。这为后续从endWord向beginWord回溯提供了统一的数据结构。6.4 DFS 回溯def dfs_backtrack(node: str, path: List[str]): if node beginWord: results.append(path[::-1]) return for parent in parents[node]: path.append(parent) dfs_backtrack(parent, path) path.pop()递归函数清晰简洁。path参数保存了当前回溯的路径。path[::-1]进行反转因为回溯是从终点到起点而我们需要的是从起点到终点的路径。使用path.pop()进行回溯这是标准的 DFS 回溯模板。7. 复杂度分析与性能观察7.1 时间复杂度构建图BFS 部分最坏情况下每个单词都需要生成 L * 26 个邻居并检查是否在集合中O(1)。对于 N 个单词这部分是 O(N * L * 26)。但实际由于 BFS 的层级特性不会访问所有单词的所有邻居。BFS 遍历每个单词最多被访问一次进入队列每次访问时生成邻居。所以可以粗略认为 BFS 部分时间复杂度为 O(N * L * 26)。DFS 回溯在最坏情况下如果图中每层节点都完全连接最短路径的数量可能是指数级的。例如如果每一层都有 k 个节点且它们都互相连接那么路径数可能达到 O(k^d)其中 d 为路径长度。因此DFS 回溯的时间复杂度与输出结果的数量成正比属于输出敏感型。这是问题本身固有的复杂度无法避免。总复杂度通常表示为 O(N * L * 26 V E Output)其中 V 是节点数E 是边数在单词接龙问题中E 可能与 NL26 同阶。7.2 空间复杂度wordSet: O(N)parents字典存储每个单词及其父节点集合。最坏情况下每个单词都可能被其他多个单词指向因此空间复杂度为 O(N * avg_parents)平均父节点数通常较小。BFS 队列和已访问集合O(N)DFS 递归栈深度为最短路径长度 d即 O(d)。总空间复杂度O(N * L) 级别主要取决于单词数量和单词长度。7.3 性能实测建议你可以使用以下代码片段进行简单的性能测试和观察import time def test_performance(): solution Solution() # 构造一个中等规模的测试用例 beginWord aaaa endWord zzzz # 生成一个单词列表包含所有4字母单词部分 # 注意这里仅为示例实际测试可使用更大的数据集 wordList [] letters abcdefghijklmnopqrstuvwxyz # 生成一些模式化的单词例如改变一个字母 base list(beginWord) for i in range(len(base)): for c in letters: if c base[i]: continue new_word base.copy() new_word[i] c wordList.append(.join(new_word)) # 确保endWord在列表中 if endWord not in wordList: wordList.append(endWord) print(f单词表大小: {len(wordList)}) start_time time.time() result solution.findLadders(beginWord, endWord, wordList) end_time time.time() print(f计算耗时: {end_time - start_time:.4f} 秒) print(f找到路径数: {len(result)}) if result: print(f最短路径长度: {len(result[0])}) # 打印前3条路径 for i, path in enumerate(result[:3]): print(f 路径{i1}: {path}) if __name__ __main__: test_performance()运行这个测试你可以观察算法在你本地机器上的执行时间并理解单词表规模N和单词长度L对性能的影响。8. 常见问题与排查方法在实现和调试该算法时你可能会遇到以下问题问题现象可能原因排查方式解决方案结果为空列表1.endWord不在wordList中。2.beginWord无法通过改变一个字母转换成wordList中的任何单词。3.beginWord到endWord本身就不连通。1. 检查输入确认endWord in wordList。2. 手动模拟几个步骤看是否存在路径。3. 使用 BFS 只找长度LeetCode 127题先验证连通性。确保输入正确。如果确实无解返回[]是正确行为。结果缺少某些路径1. 在 BFS 记录父子关系时当遇到已访问节点没有处理同一层级的情况。2.parents字典使用不当例如用列表存储但未去重导致重复路径。1. 检查 BFS 代码中当next_word已被访问且层级相同时是否仍然添加了父子关系。2. 使用set存储父节点自动去重。确保 BFS 中同一层级访问到同一个节点时要记录所有来源父节点。这是找到所有路径的关键。DFS 回溯时递归深度过大或栈溢出1. 图中存在环导致 DFS 无限循环。2.parents关系记录错误形成了循环引用。1. 检查parents图确保它是有向无环图 (DAG)。在 BFS 构建时子节点的层级一定大于父节点所以天然无环。2. 打印parents字典检查是否有异常。BFS 按层构建的关系图应该是无环的。如果出现栈溢出检查 Python 递归深度限制对于极深路径可考虑用迭代栈实现 DFS。算法运行超时1. 单词表很大N 5000且单词长度 L 也较大。2. 使用了低效的邻居生成方式如两两比较。3. 最短路径数量极多DFS 输出耗时。1. 分析时间瓶颈。使用性能分析工具或打印时间戳。2. 确认邻居生成是 O(26*L) 而非 O(N²)。3. 对于输出极多的情况算法本身复杂度就高需要考虑剪枝或问题是否可简化。1. 确保使用set进行 O(1) 查找。2. 使用双向 BFS 减少搜索空间。3. 如果仅需路径数量或一条路径应使用更简单的 BFS。parents字典方向混乱DFS 找不到beginWord双向 BFS 中reverse标志位逻辑错误导致父子关系记录反了。单步调试或打印reverse标志和parents记录语句确认parent和child的对应关系。仔细理解代码中reverse的逻辑当搜索方向是begin-end时current_word是parent方向是end-begin时current_word是child。9. 最佳实践与扩展建议9.1 编码最佳实践使用类型注解如List[str],Dict[str, Set[str]]等提高代码可读性和 IDE 支持。善用数据结构collections.defaultdict(set)避免键不存在的判断。set用于去重和快速查找。deque用于需要高效 popleft 的队列虽然本例中用了set做层级遍历但deque在标准 BFS 中更常见。函数拆分将 BFS 构建图和 DFS 回溯拆分成独立函数如_bfs()和_dfs()使主函数findLadders更清晰。添加详细注释对于复杂算法注释能帮助他人以及未来的你理解关键步骤。9.2 算法扩展与变种仅需一条最短路径使用标准 BFS并在访问节点时记录其前驱节点单个找到终点后反向构造路径即可。复杂度更低。需要所有路径不限于最短这是一个 NP-Hard 问题在一般图中找所有简单路径需要回溯剪枝对于大图不可行。单词长度可变或规则变化修改邻居生成函数即可适应。例如允许交换相邻字母、增加或删除字母等。超大单词表如果 N 极大如 10^5O(NL26) 的建图可能内存不足。可以考虑虚拟节点法将单词hot拆分为*ot,h*t,ho*三个模式。所有共享同一模式的单词互为邻居。这样可以将边数从 O(N²) 降到 O(N*L)但需要更多内存存储模式映射。数据库或外部存储对于无法全部装入内存的单词表需要借助外部存储和索引。9.3 面试技巧先澄清问题确认是否要所有最短路径还是一条即可。从简单开始可以先阐述单向 BFS 找最短长度127题的思路然后引出记录所有路径的难点。逐步优化提出朴素 DFS 的缺陷 - 引入 BFS 确定最短路径长度 - 提出在 BFS 中记录父子关系 - 最后讨论双向 BFS 优化。分析复杂度主动分析时间、空间复杂度特别是 DFS 部分与输出数量相关。编写代码按照讨论的思路模块化地编写代码并解释关键行。理解并掌握“单词接龙 II”的解法不仅能帮你解决这道具体的题目更能让你深刻理解图搜索与回溯的结合以及双向 BFS这种优化技巧。这种将问题建模为图并通过分层搜索构建解空间树的思想在许多其他场景如社交网络分析、状态空间搜索中同样适用。建议你将代码运行几遍用不同的测试用例进行调试并尝试自己从头实现以巩固理解。 LeetCode 126题解析：双向BFS与DFS回溯找出所有最短单词转换路径
这次我们来看 LeetCode 第 126 题“单词接龙 II”。这道题是“单词接龙 I”的进阶版不仅要求找到最短转换序列的长度还要找出所有可能的最短转换序列本身。它综合考察了图论BFS/DFS、字符串处理和回溯算法是面试中的高频难题。很多人在处理“找出所有路径”时容易超时或内存溢出本文将用 Python 带你拆解问题本质并提供一套清晰、高效且可复现的解决方案。核心挑战在于如何高效地构建单词间的转换关系图并利用广度优先搜索BFS找到最短路径的层级结构最后通过深度优先搜索DFS回溯出所有具体路径。盲目地进行 DFS 搜索会带来指数级的时间开销。本文将重点讲解双向 BFS 构建搜索树与DFS 回溯相结合的经典解法并分析其时间与空间复杂度。无论你是正在准备面试还是希望提升算法思维这套方法都能直接应用。本文将带你完成以下内容首先理解问题并分析难点然后详细拆解双向 BFS 构建邻接关系的步骤接着展示如何通过 DFS 回溯所有最短路径最后提供完整的 Python 代码实现、测试用例以及复杂度分析。我们重点关注算法的通用性和在不同规模输入下的表现。1. 核心能力速览在深入代码之前我们先通过一个表格快速了解本解法的核心特性和要求能力项说明问题类型图论搜索、回溯算法、字符串处理核心算法双向广度优先搜索 (Bidirectional BFS) 深度优先搜索 (DFS)时间复杂度O(N * L * 26 V E)其中 N 为单词表长度L 为单词长度。构建图占主导。空间复杂度O(N * L) 用于存储图结构和搜索过程中的队列、集合。关键优化点1. 使用双向 BFS 加速搜索并确定最短路径长度。2. 在 BFS 过程中记录每个单词的“父节点”关系构建出搜索树。3. 使用 DFS 在搜索树上回溯生成所有最短路径避免全图 DFS。输入/输出格式输入:beginWord(str),endWord(str),wordList(List[str])输出:List[List[str]]所有最短转换序列。适合场景面试算法准备、理解图搜索与回溯的结合、解决需要输出所有解的组合优化问题。不适合场景单词表极大如超过 5000且单词长度也很长时构建图的 O(NL26) 操作可能成为瓶颈需考虑更优的建图策略。2. 问题重述与难点分析题目要求 给定一个起始单词beginWord、一个结束单词endWord和一个单词列表wordList。需要找出从beginWord到endWord的所有最短转换序列。转换规则如下每次转换只能改变一个字母。转换过程中的每个中间单词必须是wordList中的单词beginWord不需要在列表中但endWord必须在。示例输入 beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log,cog] 输出 [ [hit,hot,dot,dog,cog], [hit,hot,lot,log,cog] ]难点分析找出所有路径而非一条这是与第 127 题单词接龙 I的本质区别。简单的 BFS 只能找到一条路径或最短长度无法记录所有分支。避免指数级搜索最朴素的想法是从起点开始 DFS但单词表构成一张图DFS 可能会探索所有可能的路径时间复杂度过高。确定搜索边界我们需要知道最短路径的长度是多少才能在这个边界内进行有效搜索避免搜索过深。高效构建邻居关系如何快速判断两个单词是否只差一个字母直接两两比较是 O(N² * L)对于较大的 N 不可接受。解决方案思路 采用双向 BFS 构建搜索树 DFS 回溯的策略。阶段一双向 BFS从起点和终点同时开始进行层级扩散的 BFS。当两边搜索相遇时我们就确定了最短路径长度并且在搜索过程中我们会记录每个单词是从哪些“父单词”扩展而来的。这形成了一棵或多棵反向的搜索树树根是endWord。阶段二DFS 回溯从endWord出发沿着阶段一记录的“父节点”关系反向 DFS 回溯到beginWord即可构造出所有从起点到终点的最短路径。这个方法的关键在于BFS 保证了我们找到的是最短路径层级而记录的父子关系为我们后续 DFS 提供了精确的、不会绕远路的搜索空间。3. 环境准备与算法依赖本算法实现不依赖特定的第三方库只需要标准的 Python 环境。但为了更好的开发体验建议进行如下准备Python 环境推荐 Python 3.8 及以上版本。可以在终端使用python --version检查。代码编辑器/IDEVS Code, PyCharm, Jupyter Notebook 等均可。理解基础数据结构算法中会频繁使用set集合、dict字典、deque双端队列、list列表和defaultdict默认字典。确保你了解它们的时间复杂度。set: 用于 O(1) 时间判断成员是否存在。dict/defaultdict: 用于存储图结构和父子关系。deque: 用于 BFS 队列提供高效的 popleft 操作。算法前置知识广度优先搜索 (BFS)层级遍历思想。深度优先搜索 (DFS)递归或栈实现回溯。图的表示邻接表。在本问题中我们不会显式构建完整的图而是动态生成邻居。核心数据结构设计wordSet: 将wordList转为集合用于 O(1) 的查找。parents: 一个字典键为单词值为一个集合存储该单词的所有“父节点”即在 BFS 中能一步转换到该单词的那些单词。这个结构是构建搜索树的关键。queue: BFS 使用的队列。visited: 记录在当前层级已访问过的单词避免重复访问同一层级注意不同路径在同一层级访问同一单词是允许的这是找到所有路径的关键。4. 算法步骤详细拆解4.1 步骤一预处理与初始化首先进行边界条件检查和数据准备。将wordList转换为集合wordSet提高查找效率。检查endWord是否在wordSet中如果不在直接返回空列表[]因为不可能到达。初始化数据结构queue collections.deque([beginWord])单向 BFS 初始化双向 BFS 稍复杂visited set([beginWord])记录已访问节点。parents collections.defaultdict(set)记录父子关系。found False标记是否已找到最短路径。level 0当前 BFS 的层级。为了支持双向 BFS我们还需要一个从终点开始的队列和访问集合但更常见的实现是使用一个队列但在每层循环中交替处理“当前层所有节点”。为了清晰我们先讲解单向 BFS 记录父子关系的原理再扩展到双向 BFS。4.2 步骤二单向 BFS 构建父子关系树原理在标准的层级 BFS 中我们遍历当前队列中的所有单词即同一层的单词对于每个单词生成其所有可能的“下一个单词”即改变一个字母且在wordSet中的单词。如果这个“下一个单词”没有被访问过则将其加入队列和已访问集合并记录父子关系parents[next_word].add(current_word)。如果这个“下一个单词”已经被访问过但访问它的层级与当前层级相同即它是在本层由其他单词扩展出来的那么我们仍然需要记录这个新的父子关系因为这是另一条最短路径。这是实现“记录所有最短路径”的关键。如果“下一个单词”是endWord我们标记found True。注意此时不要立即停止需要完成当前层的所有遍历以确保收集到本层所有能到达endWord的路径。当一层遍历结束后如果found为True则 BFS 结束。此时parents字典中就存储了从beginWord到endWord最短路径上的所有父子关系。生成邻居的优化技巧 对于单词word逐个位置尝试将其替换为 ‘a’ 到 ‘z’ 的 26 个字母生成新单词new_word判断new_word是否在wordSet中。时间复杂度为 O(26 * L)其中 L 为单词长度。这比两两比较单词 (O(N²)) 高效得多。4.3 步骤三双向 BFS 优化单向 BFS 从起点扩散直到遇到终点。搜索空间近似为一个球形。双向 BFS 同时从起点和终点扩散当两个搜索球相遇时停止可以显著减少搜索的节点数尤其当分支因子较大时。实现细节我们使用两个集合begin_queue和end_queue实际用set表示当前层节点更方便以及begin_visited和end_visited字典记录单词和其对应的层级。每次迭代选择节点数较少的那一端进行扩展平衡两端搜索速度。在扩展某一端的当前层时对于每个单词生成邻居。如果生成的邻居在另一端的已访问集合中说明两端相遇最短路径找到。在扩展过程中同样需要记录父子关系。为了后续 DFS 回溯方便我们通常固定从终点向起点回溯。因此在 BFS 过程中我们始终记录parents[child_word] parent_word并且 BFS 的方向是从起点向终点或者通过一些技巧保证parents关系的方向一致。为了简化理解和代码实现许多成功的解法采用了一次 BFS从起点开始来构建parents关系图因为这对于找出所有最短路径已经足够。双向 BFS 主要用于快速确定最短路径长度和减少构建parents图时的搜索空间。下面的代码实现将展示结合了双向 BFS 思想来加速搜索的版本。4.4 步骤四DFS 回溯所有路径BFS 结束后我们得到了parents图和found标志。如果found为True我们就可以进行 DFS 回溯。起点endWord终点beginWord路径我们从endWord开始将其加入当前路径。递归过程对于当前单词current在parents[current]中找到它的所有父单词。对每个父单词递归调用 DFS。终止条件当current beginWord时说明我们已经回溯到了起点。此时当前路径是一条从endWord到beginWord的逆序路径。我们需要将其反转然后加入到最终结果列表中。由于parents图是在 BFS 按层级构建的它保证了回溯出的任何路径长度都是最短的。5. 完整 Python 代码实现与注释以下是结合了双向 BFS 优化和 DFS 回溯的完整代码实现。代码包含了详细的注释帮助你理解每一步。from collections import defaultdict, deque from typing import List class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) - List[List[str]]: # 步骤1: 预处理将wordList转为集合并检查endWord是否存在 wordSet set(wordList) if endWord not in wordSet: return [] # 移除beginWord避免后续处理中的干扰如果它在列表中 wordSet.discard(beginWord) # 步骤2: 初始化数据结构 # parents 记录每个单词的父节点集合哪些单词可以一步转换到它 parents defaultdict(set) # 使用双向BFS初始化两个队列和已访问字典记录单词和其所在层级 begin_queue {beginWord} end_queue {endWord} begin_visited {beginWord: 0} # 单词层级 end_visited {endWord: 0} found False reverse False # 方向标志False表示从begin向end扩展True表示从end向begin扩展 depth 0 # 步骤3: 双向BFS构建parents图 while begin_queue and not found: depth 1 next_level set() # 遍历当前层的所有单词 for current_word in begin_queue: # 生成当前单词的所有可能邻居 for i in range(len(current_word)): for c in abcdefghijklmnopqrstuvwxyz: if c current_word[i]: continue next_word current_word[:i] c current_word[i1:] # 关键逻辑开始 if next_word in wordSet or next_word in end_visited: # 如果next_word在另一端已被访问说明相遇 if next_word in end_visited: found True # 记录父子关系。注意方向我们希望parents[child] parent # 当前搜索方向是 begin - end所以 current_word 是 parent, next_word 是 child # 但如果reverse为True说明当前是从end向begin搜索关系要反过来 if not reverse: parents[next_word].add(current_word) else: parents[current_word].add(next_word) # 如果next_word未被本端访问过则加入下一层 if next_word not in begin_visited: begin_visited[next_word] depth next_level.add(next_word) # 准备下一层 begin_queue next_level # 交换两端队列和访问字典实现交替扩展总是扩展较小的一端 if len(begin_queue) len(end_queue): begin_queue, end_queue end_queue, begin_queue begin_visited, end_visited end_visited, begin_visited reverse not reverse # 交换方向时方向标志取反 # 步骤4: 如果未找到路径返回空列表 if not found: return [] # 步骤5: DFS回溯收集所有最短路径 results [] def dfs_backtrack(node: str, path: List[str]): 从当前节点node回溯到beginWord if node beginWord: # 找到一条完整路径当前path是从endWord到beginWord的逆序 results.append(path[::-1]) # 反转路径并加入结果 return # 遍历当前节点的所有父节点 for parent in parents[node]: path.append(parent) dfs_backtrack(parent, path) path.pop() # 回溯 # 从endWord开始回溯 dfs_backtrack(endWord, [endWord]) return results # 测试代码 if __name__ __main__: solution Solution() # 测试用例1: 题目示例 beginWord hit endWord cog wordList [hot,dot,dog,lot,log,cog] print(测试用例1:) print(f输入: beginWord{beginWord}, endWord{endWord}, wordList{wordList}) result solution.findLadders(beginWord, endWord, wordList) print(f输出: {result}) print(预期: [[hit,hot,dot,dog,cog], [hit,hot,lot,log,cog]]) print() # 测试用例2: 无解情况 beginWord hit endWord cog wordList [hot,dot,dog,lot,log] # 缺少cog print(测试用例2 (无解):) print(f输入: beginWord{beginWord}, endWord{endWord}, wordList{wordList}) result solution.findLadders(beginWord, endWord, wordList) print(f输出: {result}) print(预期: []) print() # 测试用例3: 更复杂的例子 beginWord red endWord tax wordList [ted,tex,red,tax,tad,den,rex,pee] print(测试用例3:) print(f输入: beginWord{beginWord}, endWord{endWord}, wordList{wordList}) result solution.findLadders(beginWord, endWord, wordList) print(f输出: {result}) # 预期路径之一: [red,ted,tad,tax] # 预期路径之二: [red,ted,tex,tax] # 预期路径之三: [red,rex,tex,tax] print(f找到 {len(result)} 条路径。) for path in result: print(f {path})6. 代码逐段解析与关键点6.1 数据结构初始化wordSet set(wordList) if endWord not in wordSet: return [] wordSet.discard(beginWord)使用set是为了 O(1) 的查找时间复杂度这是性能的基础。提前检查endWord可避免无谓的搜索。discard移除beginWord防止它干扰邻居生成因为它可能不在原始列表中也可能在。6.2 双向 BFS 循环逻辑while begin_queue and not found: depth 1 next_level set() for current_word in begin_queue: # ... 生成邻居并处理 ... begin_queue next_level # 交换两端队列总是扩展较小的一端begin_queue和end_queue使用set而不是deque因为在这一层我们只需要遍历集合中的所有元素而不关心顺序。set还能自动去重。next_level也是一个set用于收集下一层要扩展的单词。交换队列这是一个重要优化。每次扩展后比较两端待扩展集合的大小选择较小的那个进行下一轮扩展这有助于平衡搜索尽快相遇。6.3 邻居生成与父子关系记录for i in range(len(current_word)): for c in abcdefghijklmnopqrstuvwxyz: if c current_word[i]: continue next_word current_word[:i] c current_word[i1:] if next_word in wordSet or next_word in end_visited: # ... 判断相遇和记录关系 ...邻居生成复杂度为 O(26*L)对于 L5 的单词最多生成 130 个候选比比较整个单词表高效。if next_word in wordSet or next_word in end_visited:这个条件很关键。wordSet是合法单词库end_visited包含了另一端已访问的单词即使它可能不在原始wordList中比如beginWord。这保证了搜索的正确性。父子关系方向reverse标志位确保了无论从哪一端扩展parents[child]中存储的始终是parent即parent - child是搜索进行的方向。这为后续从endWord向beginWord回溯提供了统一的数据结构。6.4 DFS 回溯def dfs_backtrack(node: str, path: List[str]): if node beginWord: results.append(path[::-1]) return for parent in parents[node]: path.append(parent) dfs_backtrack(parent, path) path.pop()递归函数清晰简洁。path参数保存了当前回溯的路径。path[::-1]进行反转因为回溯是从终点到起点而我们需要的是从起点到终点的路径。使用path.pop()进行回溯这是标准的 DFS 回溯模板。7. 复杂度分析与性能观察7.1 时间复杂度构建图BFS 部分最坏情况下每个单词都需要生成 L * 26 个邻居并检查是否在集合中O(1)。对于 N 个单词这部分是 O(N * L * 26)。但实际由于 BFS 的层级特性不会访问所有单词的所有邻居。BFS 遍历每个单词最多被访问一次进入队列每次访问时生成邻居。所以可以粗略认为 BFS 部分时间复杂度为 O(N * L * 26)。DFS 回溯在最坏情况下如果图中每层节点都完全连接最短路径的数量可能是指数级的。例如如果每一层都有 k 个节点且它们都互相连接那么路径数可能达到 O(k^d)其中 d 为路径长度。因此DFS 回溯的时间复杂度与输出结果的数量成正比属于输出敏感型。这是问题本身固有的复杂度无法避免。总复杂度通常表示为 O(N * L * 26 V E Output)其中 V 是节点数E 是边数在单词接龙问题中E 可能与 NL26 同阶。7.2 空间复杂度wordSet: O(N)parents字典存储每个单词及其父节点集合。最坏情况下每个单词都可能被其他多个单词指向因此空间复杂度为 O(N * avg_parents)平均父节点数通常较小。BFS 队列和已访问集合O(N)DFS 递归栈深度为最短路径长度 d即 O(d)。总空间复杂度O(N * L) 级别主要取决于单词数量和单词长度。7.3 性能实测建议你可以使用以下代码片段进行简单的性能测试和观察import time def test_performance(): solution Solution() # 构造一个中等规模的测试用例 beginWord aaaa endWord zzzz # 生成一个单词列表包含所有4字母单词部分 # 注意这里仅为示例实际测试可使用更大的数据集 wordList [] letters abcdefghijklmnopqrstuvwxyz # 生成一些模式化的单词例如改变一个字母 base list(beginWord) for i in range(len(base)): for c in letters: if c base[i]: continue new_word base.copy() new_word[i] c wordList.append(.join(new_word)) # 确保endWord在列表中 if endWord not in wordList: wordList.append(endWord) print(f单词表大小: {len(wordList)}) start_time time.time() result solution.findLadders(beginWord, endWord, wordList) end_time time.time() print(f计算耗时: {end_time - start_time:.4f} 秒) print(f找到路径数: {len(result)}) if result: print(f最短路径长度: {len(result[0])}) # 打印前3条路径 for i, path in enumerate(result[:3]): print(f 路径{i1}: {path}) if __name__ __main__: test_performance()运行这个测试你可以观察算法在你本地机器上的执行时间并理解单词表规模N和单词长度L对性能的影响。8. 常见问题与排查方法在实现和调试该算法时你可能会遇到以下问题问题现象可能原因排查方式解决方案结果为空列表1.endWord不在wordList中。2.beginWord无法通过改变一个字母转换成wordList中的任何单词。3.beginWord到endWord本身就不连通。1. 检查输入确认endWord in wordList。2. 手动模拟几个步骤看是否存在路径。3. 使用 BFS 只找长度LeetCode 127题先验证连通性。确保输入正确。如果确实无解返回[]是正确行为。结果缺少某些路径1. 在 BFS 记录父子关系时当遇到已访问节点没有处理同一层级的情况。2.parents字典使用不当例如用列表存储但未去重导致重复路径。1. 检查 BFS 代码中当next_word已被访问且层级相同时是否仍然添加了父子关系。2. 使用set存储父节点自动去重。确保 BFS 中同一层级访问到同一个节点时要记录所有来源父节点。这是找到所有路径的关键。DFS 回溯时递归深度过大或栈溢出1. 图中存在环导致 DFS 无限循环。2.parents关系记录错误形成了循环引用。1. 检查parents图确保它是有向无环图 (DAG)。在 BFS 构建时子节点的层级一定大于父节点所以天然无环。2. 打印parents字典检查是否有异常。BFS 按层构建的关系图应该是无环的。如果出现栈溢出检查 Python 递归深度限制对于极深路径可考虑用迭代栈实现 DFS。算法运行超时1. 单词表很大N 5000且单词长度 L 也较大。2. 使用了低效的邻居生成方式如两两比较。3. 最短路径数量极多DFS 输出耗时。1. 分析时间瓶颈。使用性能分析工具或打印时间戳。2. 确认邻居生成是 O(26*L) 而非 O(N²)。3. 对于输出极多的情况算法本身复杂度就高需要考虑剪枝或问题是否可简化。1. 确保使用set进行 O(1) 查找。2. 使用双向 BFS 减少搜索空间。3. 如果仅需路径数量或一条路径应使用更简单的 BFS。parents字典方向混乱DFS 找不到beginWord双向 BFS 中reverse标志位逻辑错误导致父子关系记录反了。单步调试或打印reverse标志和parents记录语句确认parent和child的对应关系。仔细理解代码中reverse的逻辑当搜索方向是begin-end时current_word是parent方向是end-begin时current_word是child。9. 最佳实践与扩展建议9.1 编码最佳实践使用类型注解如List[str],Dict[str, Set[str]]等提高代码可读性和 IDE 支持。善用数据结构collections.defaultdict(set)避免键不存在的判断。set用于去重和快速查找。deque用于需要高效 popleft 的队列虽然本例中用了set做层级遍历但deque在标准 BFS 中更常见。函数拆分将 BFS 构建图和 DFS 回溯拆分成独立函数如_bfs()和_dfs()使主函数findLadders更清晰。添加详细注释对于复杂算法注释能帮助他人以及未来的你理解关键步骤。9.2 算法扩展与变种仅需一条最短路径使用标准 BFS并在访问节点时记录其前驱节点单个找到终点后反向构造路径即可。复杂度更低。需要所有路径不限于最短这是一个 NP-Hard 问题在一般图中找所有简单路径需要回溯剪枝对于大图不可行。单词长度可变或规则变化修改邻居生成函数即可适应。例如允许交换相邻字母、增加或删除字母等。超大单词表如果 N 极大如 10^5O(NL26) 的建图可能内存不足。可以考虑虚拟节点法将单词hot拆分为*ot,h*t,ho*三个模式。所有共享同一模式的单词互为邻居。这样可以将边数从 O(N²) 降到 O(N*L)但需要更多内存存储模式映射。数据库或外部存储对于无法全部装入内存的单词表需要借助外部存储和索引。9.3 面试技巧先澄清问题确认是否要所有最短路径还是一条即可。从简单开始可以先阐述单向 BFS 找最短长度127题的思路然后引出记录所有路径的难点。逐步优化提出朴素 DFS 的缺陷 - 引入 BFS 确定最短路径长度 - 提出在 BFS 中记录父子关系 - 最后讨论双向 BFS 优化。分析复杂度主动分析时间、空间复杂度特别是 DFS 部分与输出数量相关。编写代码按照讨论的思路模块化地编写代码并解释关键行。理解并掌握“单词接龙 II”的解法不仅能帮你解决这道具体的题目更能让你深刻理解图搜索与回溯的结合以及双向 BFS这种优化技巧。这种将问题建模为图并通过分层搜索构建解空间树的思想在许多其他场景如社交网络分析、状态空间搜索中同样适用。建议你将代码运行几遍用不同的测试用例进行调试并尝试自己从头实现以巩固理解。