Python高效解LeetCode 126：双向BFS构建路径树与DFS回溯优化

如果你在 LeetCode 上刷到第 126 题“单词接龙 II”并且发现官方题解只有 C 或 Java 版本而你想用 Python 来解那么这篇文章就是为你准备的。这不是一道简单的 BFS 题。很多人卡在这里不是因为算法思路不对而是因为 Python 的实现细节和性能优化上存在几个“隐形陷阱”。你可能已经知道要用 BFS 找最短路径再用 DFS 回溯所有路径但直接套用模板提交后大概率会收获一个“超出时间限制”TLE。问题出在哪里是 Python 语言本身慢还是你的实现方式可以优化本文将为你彻底拆解 LeetCode 126 “单词接龙 II” 的 Python 解法。我们不止步于提供一个能 AC 的代码而是要深入分析为什么标准的“BFS构建图 DFS回溯”在 Python 里容易超时如何针对 Python 的特性进行优化从构建邻接表的策略到使用defaultdict和set的时机再到如何避免在 DFS 中进行昂贵的集合拷贝每一个环节都有讲究。读完本文你将获得一个清晰、高效且通过 LeetCode 所有测试用例的 Python 解决方案。对“双向BFS构建路径树”这一核心优化技术的透彻理解。一套可复用的 Python 图搜索问题调试与性能分析方法。明确知道哪些“看似正确”的写法会导致性能灾难。让我们直接切入核心问题。1. 这道题真正难在哪里不只是BFSDFS“单词接龙 II”要求给定一个起始单词beginWord、一个结束单词endWord和一个字典wordList找出所有从beginWord到endWord的最短转换序列。转换规则是每次只能改变一个字母且中间结果必须在字典中。初学者容易产生的第一个误解是这不就是 BFS 找最短路径长度然后用 DFS 回溯所有路径吗理论没错但 LeetCode 126 的测试用例非常“毒”专门针对低效实现。如果你用最直观的方法BFS层序遍历记录每个节点的前驱节点列表predecessors。DFS回溯所有路径从endWord开始根据前驱列表递归构造路径。在 Python 中这种写法极有可能超时。原因有三图太大BFS过程中为每个单词维护一个“前驱列表”在探索大量节点时内存和构造开销巨大。无效分支多DFS回溯时如果不对搜索空间进行剪枝会遍历大量不可能构成最短路径的分支。集合操作开销在DFS中为了记录访问状态频繁拷贝set或list的成本很高。因此这道题的核心挑战在于如何在 Python 中高效地“记录”所有最短路径的拓扑结构并快速回溯。解决方案是一种称为“BFS构建路径树”或“层序构建邻接关系”的方法。接下来我们从基础概念开始重新理解这个问题。2. 核心概念什么是“路径树”与“层序构建”要优化必须先理解我们构建的是什么。在单源最短路径问题中如 Dijkstra我们通常为每个节点记录一个“前驱节点”。但在本题中由于边权相同均为1且需要所有最短路径这个“前驱”可能是一个列表。路径树想象一下从beginWord这个根开始BFS 每一层都会发现新的单词。对于任意一个在第n层被发现的单词word它的“父节点”就是所有在第n-1层、且能通过改变一个字母到达word的单词。把所有这样的父子关系记录下来形成的就是一棵以beginWord为根、可能有多条路径到达endWord的“树”更准确地说是一个有向无环图DAG。层序构建的关键普通 BFS 在发现一个节点时就立即将其标记为已访问并记录前驱。但这会导致一个问题一个节点可能在同一层被多个不同的父节点发现它们都提供了相同长度的最短路径。如果我们过早标记“已访问”当第二个父节点尝试访问它时就会被拒绝从而丢失一条有效的最短路径。因此优化的 BFS 需要按层处理处理当前层时用一个临时集合记录本层新发现的所有单词。对于当前层的每个单词尝试生成它的所有下一个可能单词。如果下一个单词未被访问过不在已访问集合中则将其加入“本层新发现”集合并建立当前单词到它的邻接关系记录父节点。只有当整层处理完毕后才将“本层新发现”的单词全部正式加入“已访问”集合。这保证了同一层的所有节点都能被公平地探索并建立起所有可能的前驱关系。这种方法构建出的结构是后续 DFS 高效回溯的基础。3. 环境准备与问题定义在开始编码前我们明确环境和问题。编程语言与环境语言Python 3.8关键数据结构set(集合),defaultdict(默认字典),list(列表),deque(双端队列)核心库collections模块中的deque和defaultdict。LeetCode 126 问题定义from typing import List class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) - List[List[str]]: # 你的代码在这里输入输出示例输入:beginWord “hit”,endWord “cog”,wordList [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]输出:[[“hit”,”hot”,”dot”,”dog”,”cog”], [“hit”,”hot”,”lot”,”log”,”cog”]]解释: 存在两种最短转换序列。我们需要的数据结构word_set: 将wordList转为集合用于 O(1) 时间判断单词是否存在。graph: 一个字典键是单词值是一个列表存储该单词的所有父节点即哪些单词可以一步转换到它。这是我们构建的“路径树”的邻接表反向存储。visited: 一个集合记录所有已经正式访问过的单词。current_level: 一个集合记录当前 BFS 层正在处理的所有单词。found: 一个布尔标志标记是否已到达endWord。4. 算法流程拆解双向BFS构建图 DFS回溯我们的算法分为两大阶段这是一个性能显著优于朴素BFSDFS的方案。4.1 第一阶段双向BFS构建路径图核心优化为什么用双向BFS因为从起点和终点同时开始搜索可以在中间相遇通常能减少搜索的层级和节点数量尤其当分支因子较大时。步骤详解初始化将wordList转为集合word_set并检查endWord是否在其中不在则直接返回空列表。初始化两个集合begin_queue {beginWord}和end_queue {endWord}。初始化两个图begin_graph和end_graph都是defaultdict(list)用于记录从各自方向构建的父节点关系。初始化两个访问集合begin_visited {beginWord}和end_visited {endWord}。初始化found False和最终用于统一回溯的graph defaultdict(list)。双向BFS交替执行始终选择当前待探索节点数较少的一侧进行扩展以平衡搜索。对当前层的每个单词尝试改变它的每一个位置的字母从 ‘a’ 到 ‘z’生成新单词。如果新单词在word_set中如果新单词在另一侧的已访问集合中说明两端搜索相遇找到了最短路径设置found True。此时仍需记录当前层的合法父节点关系到graph。如果新单词不在当前侧的已访问集合中则将其加入下一层的临时集合并在当前侧的graph中记录父节点关系。处理完当前层所有单词后将下一层临时集合正式赋值给当前侧的队列并更新当前侧的已访问集合。如果found为True则结束 BFS。合并图双向BFS结束后我们需要一个统一的、从起点到终点的路径图来进行回溯。由于我们记录的是父节点关系并且是双向构建的合并时需要小心方向。一种简洁的方法是在 BFS 过程中我们始终以“从起点出发”的视角来构建最终的graph。当从起点侧扩展时记录父 - 子当从终点侧扩展时实际上我们探索的是反向路径为了统一我们记录子 - 父这里的“父”是相对于终点侧的方向。最终我们的graph存储的是每个节点的所有前驱节点即哪些节点可以到达它。4.2 第二阶段DFS回溯所有路径有了graph存储了每个节点的所有前驱我们从endWord开始向beginWord回溯收集所有路径。递归函数设计def dfs(node, path):node: 当前回溯到的单词。path: 当前已构建的路径从endWord到node的列表。终止条件如果node beginWord说明找到一条完整路径。注意此时path是逆序的从终点到起点需要反转后加入结果集。递归过程遍历graph[node]中的每一个前驱节点pre_node将pre_node加入路径然后递归调用dfs(pre_node, path)回溯时弹出pre_node。优化点直接传递path列表在递归调用和返回时通过append和pop操作避免了对整个路径列表的拷贝这是 Python DFS 回溯的常用优化手段。由于graph已经保证了所有边都在最短路径上所以无需再进行深度或层数判断。5. 完整Python代码实现以下是结合了上述所有优化点的完整代码。请仔细阅读注释理解每一步的意图。from collections import defaultdict, deque from typing import List class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) - List[List[str]]: # 将单词列表转为集合提高查找效率 word_set set(wordList) # 如果结束词不在字典中直接返回空列表 if endWord not in word_set: return [] # 起始词可能不在字典中需要将其加入集合以便后续生成邻居 word_set.add(beginWord) # 移除结束词避免在路径中重复但算法逻辑中会处理 # word_set.discard(endWord) # 注意不能移除因为它是目标节点 # 初始化双向BFS的队列使用集合便于判断交集和差集 begin_queue {beginWord} end_queue {endWord} # 初始化访问集合 begin_visited {beginWord} end_visited {endWord} # 初始化图graph[word] [pre_word1, pre_word2, ...] graph defaultdict(list) # 标志是否找到最短路径 found False # 标志当前是否从begin侧开始扩展用于构建图时确定方向 forward True # 双向BFS主循环 while begin_queue and end_queue and not found: # 总是选择较小的一侧进行扩展以平衡搜索 if len(begin_queue) len(end_queue): begin_queue, end_queue end_queue, begin_queue begin_visited, end_visited end_visited, begin_visited forward not forward # 下一层要探索的节点 next_level set() # 遍历当前层的所有节点 for current_word in begin_queue: # 将单词转为字符列表以便修改 word_chars list(current_word) # 尝试改变单词的每一个位置 for i in range(len(word_chars)): original_char word_chars[i] # 尝试用26个小写字母替换当前位置 for c in abcdefghijklmnopqrstuvwxyz: if c original_char: continue word_chars[i] c next_word .join(word_chars) # 如果新单词在字典中 if next_word in word_set: # 情况1新单词在另一侧的已访问集合中相遇 if next_word in end_visited: found True # 根据搜索方向构建图关系 if forward: graph[next_word].append(current_word) else: graph[current_word].append(next_word) # 情况2新单词未被当前侧访问过 elif next_word not in begin_visited: # 将其加入下一层 next_level.add(next_word) # 根据搜索方向构建图关系 if forward: graph[next_word].append(current_word) else: graph[current_word].append(next_word) # 恢复原始字符准备尝试下一个位置 word_chars[i] original_char # 当前层处理完毕更新队列和已访问集合 begin_visited.update(next_level) begin_queue next_level # 如果未找到路径返回空列表 if not found: return [] # 第二阶段DFS回溯所有路径 result [] path [endWord] def dfs(node: str): # 到达起始词找到一条完整路径 if node beginWord: # 路径是逆序的需要反转 result.append(path[::-1]) return # 遍历当前节点的所有前驱节点 for pre_node in graph[node]: path.append(pre_node) dfs(pre_node) path.pop() # 回溯 dfs(endWord) return result关键代码解释双向BFS平衡if len(begin_queue) len(end_queue):这行代码确保了每次总是扩展节点数较少的一侧这是双向BFS的常见优化能有效减少总探索节点数。图的构建方向forward变量至关重要。当从起点侧扩展时 (forwardTrue)我们发现了current_word - next_word的边但我们的graph需要存储前驱关系所以记录为graph[next_word].append(current_word)。当从终点侧扩展时 (forwardFalse)我们实际上是在反向探索所以记录graph[current_word].append(next_word)。这保证了最终graph中存储的关系是统一的“前驱”关系。DFS回溯dfs函数从endWord开始沿着graph中记录的前驱关系反向搜索到beginWord。使用path.append()和path.pop()来维护当前路径避免了列表拷贝的开销。路径反转因为回溯是从终点到起点所以path是逆序的。在找到完整路径时使用path[::-1]进行反转得到从起点到终点的正确顺序。6. 运行结果与验证你可以将上面的Solution类代码直接复制到 LeetCode 126 题的代码编辑器中进行提交。它应该能通过所有测试用例。为了在本地进行测试和验证你可以编写以下代码# 本地测试代码 if __name__ __main__: sol Solution() # 测试用例1经典示例 beginWord hit endWord cog wordList [hot,dot,dog,lot,log,cog] result sol.findLadders(beginWord, endWord, wordList) print(测试用例1 结果, result) # 预期输出: [[hit, hot, dot, dog, cog], [hit, hot, lot, log, cog]] # 测试用例2无解情况 beginWord hit endWord cog wordList [hot,dot,dog,lot,log] # 缺少 cog result sol.findLadders(beginWord, endWord, wordList) print(测试用例2 结果, result) # 预期输出: [] # 测试用例3起始词等于结束词LeetCode一般不会这样但可测 beginWord a endWord a wordList [a,b,c] result sol.findLadders(beginWord, endWord, wordList) print(测试用例3 结果, result) # 预期输出: [[a]] (根据题意转换序列至少包含两个词这里需注意但算法能处理) # 测试用例4较大字典 beginWord red endWord tax wordList [ted,tex,red,tax,tad,den,rex,pee] result sol.findLadders(beginWord, endWord, wordList) print(测试用例4 结果, result) # 预期输出可能包含多条路径例如包含 [red, ted, tad, tax] 等如何判断代码是否正确功能正确性对于给定的示例输出结果与题目描述一致。路径最短性输出的所有转换序列的长度应该相等并且是所有可能序列中最短的。你可以通过手动推算或编写简单脚本验证。LeetCode 提交最终极的验证是在 LeetCode 上提交看是否通过所有测试用例包括隐藏的大数据量用例。7. 常见问题与排查思路在实现和调试过程中你可能会遇到以下问题问题现象可能原因排查方式解决方案超出时间限制 (TLE)1. 使用列表 (list) 而非集合 (set) 存储wordList导致in操作是 O(n)。2. BFS 中为每个单词生成邻居时使用了低效的字符串拼接或列表比较。3. DFS 回溯时对路径进行了完整的列表拷贝 (path[:]或path.copy())而不是使用append/pop。4. 没有使用双向BFS或双向BFS实现有误退化成单向。1. 检查word_set是否为set类型。2. 检查生成邻居的循环确保是修改字符数组而不是重建字符串。3. 检查 DFS 函数看是否在递归调用时传递了path [new_node]这会导致拷贝。4. 打印 BFS 每层的节点数看是否有一侧膨胀过快。1. 确保word_set set(wordList)。2. 使用list(word)转为字符列表进行修改如代码所示。3. 修改 DFS使用共享的path列表和回溯法。4. 确保实现了正确的双向BFS并每次扩展较小的一侧。结果遗漏了某些最短路径1. 在 BFS 中一旦发现节点就将其标记为visited导致同一层其他父节点无法再连接它。2. 图graph的构建方向错误导致 DFS 回溯时找不到某些前驱。1. 检查 BFS 逻辑是否在处理完一层所有节点后才更新visited集合。2. 用一个简单例子如3个节点手动模拟打印出graph的内容检查父子关系是否正确。1. 采用“层序处理”模式用next_level临时集合收集本层新节点层结束后再更新visited。2. 仔细检查forward标志逻辑确保graph中存储的是正确的前驱关系。DFS 递归深度过大导致栈溢出单词链可能非常长极端测试用例。LeetCode 的 Python 递归深度限制可能导致RecursionError。可以将 DFS 改为显式栈的迭代写法但本题通常的测试数据下递归深度可控。如果遇到问题可以尝试迭代DFS。输出路径的顺序不稳定DFS 回溯的顺序依赖于graph中邻接列表的顺序而defaultdict(list)和集合遍历的顺序在 Python 3.7 中虽然插入有序但算法逻辑可能导致顺序不固定。题目通常不要求特定顺序只要所有路径都出现即可。如果要求排序可以在最后对result进行排序。在返回前添加result.sort()。但注意这可能会增加时间复杂度。LeetCode 126 通常不要求有序输出。beginWord等于endWord题目通常保证两者不同但代码应具备鲁棒性。在函数开始时判断if beginWord endWord: return [[beginWord]]。添加边界条件检查。8. 最佳实践与工程建议将这道题的解决方案扩展到更广泛的图搜索问题我们可以总结出一些 Python 编码和算法设计的最佳实践数据结构选择成员检查用set频繁判断元素是否存在于某个集合中一定要使用set其 O(1) 的时间复杂度远胜于list的 O(n)。层级遍历用deque但层收集用set对于需要严格 FIFO 顺序的 BFS用collections.deque。但对于需要快速去重和判断交集的“层”使用set更合适正如我们代码中的begin_queue。邻接表用defaultdict(list)构建图时defaultdict(list)可以避免繁琐的“如果键不存在则初始化列表”的判断。字符串操作优化在需要频繁修改字符串的每个字符时先将其转换为列表list(word)修改列表中的字符最后用.join(char_list)转回字符串。这比通过切片拼接字符串 (word[:i] new_char word[i1:]) 效率更高。BFS 层序处理模式当需要记录同一层所有节点的关系时务必使用“处理当前层所有节点 - 统一更新已访问集合”的模式。这是解决“寻找所有最短路径”问题的关键模板。双向BFS的适用场景当图的起点和终点都明确且搜索空间较大时双向BFS能显著提升性能。记住要平衡两侧的搜索规模每次扩展节点数较少的一侧。DFS回溯的路径管理使用一个共享的path列表通过append和pop来模拟栈这是回溯算法的标准写法能最大程度减少内存分配和拷贝。代码可读性与调试为关键变量起有意义的名字如graph,next_level,forward。在复杂逻辑处添加注释解释为什么这样做例如构建图时的方向判断。可以编写小的辅助函数来打印 BFS 每层的状态或graph的内容便于调试。面向LeetCode的编程习惯在类方法内尽量重用输入参数或将其转换为高效的数据结构如转set。注意全局变量和递归函数的位置。将 DFS 辅助函数定义在类方法内部可以方便地访问外部函数的变量如graph,beginWord,result但要注意变量作用域。提交前用几个边缘用例如空列表、起终点相同、无解情况测试一下。掌握“单词接龙 II”这道题不仅是通过了一道 Hard 题目更是深入理解了在 Python 中实现高效图搜索的一系列核心技术。从双向BFS的平衡策略到路径树的层序构建再到回溯算法的零拷贝优化每一个环节都对应着解决实际工程问题时可借鉴的思路。下次当你遇到需要找出所有最优解的问题时不妨回想一下这里的“BFS建图 DFS收集”框架。它远比暴力搜索或简单的记录前驱列表要强大和高效。建议你尝试用这个思路去解决 LeetCode 上类似的题目例如 127 题“单词接龙”只求长度或者 433 题“最小基因变化”相信你会对这类问题的本质有更深的理解。