在算法面试和日常刷题中单词接龙IILeetCode 126以其复杂的图论建模和路径搜索要求常常让许多开发者感到棘手。它不仅要求找到最短转换序列的长度更要求找出所有可能的最短转换序列这从“单一路径”问题升级为了“全路径”问题对算法的设计和实现都提出了更高要求。本文将围绕Python版本从问题本质出发一步步拆解BFS广度优先搜索结合DFS深度优先搜索或BFS建图再回溯的经典解法并提供完整、可运行的代码示例。无论你是正在准备面试还是希望深入理解图搜索算法这篇文章都将为你提供一套从理解到实现的完整方案。1. 问题核心与难点剖析在深入代码之前我们必须彻底理解题目在问什么以及它为什么难。问题重述LeetCode 126. 单词接龙 II 给定一个起始单词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]] 解释存在两个最短转换序列。核心难点解析找全最短路径而非一条这是与单词接龙I127题最本质的区别。127题只需求最短路径长度通常用BFS一层层遍历找到终点即可终止。而126题要求找出所有最短路径这意味着我们需要记录下所有能到达某个单词的上一层单词前驱节点以便最后能回溯出所有路径。图的结构复杂单词作为节点如果两个单词仅一个字母不同则它们之间有一条无向边。对于一个长度为L的单词它有L25种可能的单字母变换26个字母去掉自身。如果对每个单词都尝试所有可能变换并在字典中查找复杂度是O(L25*N)其中N是字典大小。如何高效地构建或遍历这个隐式图是关键。去重与剪枝在寻找所有路径时同一个单词可能在同层或不同层被多次访问。我们需要一种机制来记录每个单词是在哪一层被发现的并且只接受在同一层或更早层的前驱关系以避免路径绕圈或丢失有效路径。内存与效率的平衡存储所有前驱关系word - List[pre_word]会消耗额外空间。在BFS过程中是每层遍历完再统一记录前驱还是边遍历边记录需要仔细设计以避免逻辑错误。理解了这些难点我们就能有的放矢地设计解决方案。接下来我们将从最直观但低效的方法开始逐步优化到标准的双向BFS建图DFS回溯解法。2. 环境准备与算法思路总览在编写代码前确保你的环境已就绪并对整体算法流程有一个清晰的蓝图。开发环境建议Python版本 3.6及以上。本文代码使用Python标准库不依赖第三方包。IDE或编辑器 任何你熟悉的即可如PyCharm、VSCode、Jupyter Notebook。重点 理解算法思想比运行环境更重要。算法思路总览分层BFS建图 DFS回溯 这是解决本题最经典和高效的方法。整个过程分为两个主要阶段BFS建图阶段目标从beginWord出发进行广度优先搜索直到遇到endWord。在这个过程中不仅要找到终点还要记录下每个单词是由哪些上一层的单词转换而来的即前驱节点列表。关键数据结构queue: 用于BFS的队列。found: 布尔标志记录是否已找到endWord。level_map: 字典记录每个单词首次被发现时的层级从beginWord开始的步数。pre_map: 字典记录每个单词的所有前驱节点即哪些单词可以一步转换到它。这是后续回溯出所有路径的核心。核心策略BFS按层遍历。对于当前层的每个单词生成其所有可能的“下一个单词”如果下一个单词有效在wordList中且满足访问条件则建立从前驱到它的关系。一层遍历完成后再将本层新发现的单词加入已访问集合这是确保能记录同一层多个前驱的关键。DFS回溯阶段目标利用BFS阶段构建好的pre_map从endWord开始深度优先地回溯到beginWord从而构造出所有最短转换序列。过程这是一个标准的递归DFS。从endWord开始查找它的所有前驱单词然后递归地对每个前驱单词做同样的操作直到回溯到beginWord。将路径反转即得到一条从 begin 到 end 的序列。优化由于pre_map是在找到最短路径的前提下构建的所以回溯出的所有路径长度必然相等且最短。此外还有双向BFS的优化变种从起点和终点同时开始搜索相遇时停止可以显著减少搜索空间提升效率。我们会在基础解法之后详细讨论。下面让我们进入核心的代码实现环节。3. 基础解法单向BFS建图 DFS回溯我们先实现最直接的单向BFS方法。虽然它不是最优的但逻辑清晰是理解问题的基础。3.1 辅助函数生成邻接单词在BFS中我们需要频繁地获取一个单词的所有可能“下一跳”。最直接的方法是遍历单词的每个位置将其替换为其他25个字母检查是否在字典中。但更高效的方法是使用“通配符”预处理字典。from collections import defaultdict, deque from typing import List class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) - List[List[str]]: # 第一步预处理构建通配符字典 if endWord not in wordList: return [] word_set set(wordList) # 转换为集合实现O(1)查找 word_set.add(beginWord) # 将起始词也加入方便统一处理 # 构建模式到单词列表的映射例如 h*t - [hot, hit] pattern_dict defaultdict(list) word_len len(beginWord) for word in word_set: for i in range(word_len): pattern word[:i] * word[i1:] pattern_dict[pattern].append(word) # 第二步BFS建图 # level_map 记录单词和其所在的层级距离beginWord的步数 level_map {beginWord: 0} # pre_map 记录单词的所有前驱节点 pre_map defaultdict(list) queue deque([beginWord]) found False level 0 while queue and not found: level_size len(queue) level 1 # 本层新访问的单词用于本层遍历完后统一标记已访问 visited_this_level set() for _ in range(level_size): current_word queue.popleft() # 生成当前单词的所有可能模式并获取邻接词 for i in range(word_len): pattern current_word[:i] * current_word[i1:] for next_word in pattern_dict[pattern]: if next_word current_word: continue # 如果next_word未被访问过或者在本层被访问允许同层多前驱 if next_word not in level_map: level_map[next_word] level pre_map[next_word].append(current_word) visited_this_level.add(next_word) # 如果next_word在当前层被访问过说明是同一层的其他节点也找到了它 elif level_map[next_word] level: pre_map[next_word].append(current_word) if next_word endWord: found True # 将本层新发现的单词加入队列用于下一层扩展 for word in visited_this_level: queue.append(word) # 如果未找到终点返回空列表 if not found: return [] # 第三步DFS回溯所有路径 result [] def dfs_backtrack(node: str, path: List[str]): 从当前节点回溯到起点 if node beginWord: # 找到一条完整路径注意路径是反向的需要反转 result.append(path[::-1]) return # 遍历当前节点的所有前驱 for pre_node in pre_map[node]: path.append(pre_node) dfs_backtrack(pre_node, path) path.pop() # 回溯 # 从终点开始回溯 dfs_backtrack(endWord, [endWord]) return result # 测试代码 if __name__ __main__: sol Solution() beginWord hit endWord cog wordList [hot,dot,dog,lot,log,cog] print(sol.findLadders(beginWord, endWord, wordList)) # 预期输出: [[hit, hot, dot, dog, cog], [hit, hot, lot, log, cog]]代码关键点解释pattern_dict通配符字典这是优化邻接查找的关键。对于单词hot它会生成模式*ot,h*t,ho*。所有能匹配h*t的单词如hot,hit都被认为是相邻的。这样查找一个单词的所有邻居时间复杂度降为O(L^2)L为单词长度因为生成L个模式每个模式可能对应多个单词但平均来看比O(L*26*N)快得多。level_map与visited_this_levellevel_map记录每个单词首次被发现的层级步数。它的作用是判断一个邻居单词是否被访问过以及是否是在同一层被访问的。visited_this_level是一个临时集合用于收集本层BFS新发现的所有单词。为什么不能发现一个就立刻加入queue并标记已访问因为如果立刻标记那么同一层中其他节点可能就无法再访问这个单词从而丢失一条有效的最短路径。例如A和B在同一层都能到达C。如果A先发现C并标记B就无法记录C为邻居了。因此必须等一层全部处理完再统一将这些新单词入队并记录层级。pre_map的构建逻辑if next_word not in level_map:表示第一次发现该单词记录其层级并建立前驱关系。elif level_map[next_word] level:表示该单词在本层已经被其他节点发现过这是另一条最短路径的前驱因此需要将当前节点也加入其前驱列表。DFS回溯从endWord开始递归地查找pre_map中的前驱直到beginWord。由于我们是从终点向起点回溯所以得到的路径是反向的最后需要反转。使用path.append()和path.pop()实现标准的回溯算法。这个解法在逻辑上是正确的但对于某些极端用例单词很长、字典很大单向BFS的搜索空间可能依然很大。接下来我们看如何用双向BFS进行优化。4. 高效解法双向BFS建图 DFS回溯双向BFS的核心思想是同时从起点和终点开始搜索当两边的搜索相遇时停止。这能极大地减少搜索的层级和需要探索的节点数量尤其当分支因子较大时效果显著。双向BFS建图的特殊之处 我们需要维护两个方向的层级映射和前驱映射。当从起点方向发现一个单词已被终点方向访问过或反之即表示“相遇”找到了最短路径。此时我们需要合并两个方向的前驱信息以构建完整的pre_map。下面是双向BFS的实现代码from collections import defaultdict, deque from typing import List class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) - List[List[str]]: if endWord not in wordList: return [] word_set set(wordList) # 将起始词加入字典方便模式匹配 if beginWord not in word_set: word_set.add(beginWord) # 构建通配符字典 word_len len(beginWord) pattern_dict defaultdict(list) for word in word_set: for i in range(word_len): pattern word[:i] * word[i1:] pattern_dict[pattern].append(word) # 双向BFS初始化 # 层级记录从起点开始的距离 / 从终点开始的距离 level_begin {beginWord: 0} level_end {endWord: 0} # 前驱记录 pre_begin defaultdict(list) # key: word, value: list of previous words from begin side pre_end defaultdict(list) # key: word, value: list of next words from end side (注意方向) queue_begin deque([beginWord]) queue_end deque([endWord]) found False meet_node None forward True # 搜索方向标志True表示从begin向end搜索 while queue_begin and queue_end and not found: # 每次选择节点数较少的一边进行扩展优化搜索效率 if len(queue_begin) len(queue_end): queue, level_map, other_level_map, pre_map, forward queue_begin, level_begin, level_end, pre_begin, True else: queue, level_map, other_level_map, pre_map, forward queue_end, level_end, level_begin, pre_end, False level_size len(queue) visited_this_level set() for _ in range(level_size): current_word queue.popleft() current_level level_map[current_word] for i in range(word_len): pattern current_word[:i] * current_word[i1:] for next_word in pattern_dict[pattern]: if next_word current_word: continue # 关键判断相遇条件 if next_word in other_level_map: # 找到相遇点 found True meet_node next_word # 根据方向建立前驱关系 if forward: pre_map[next_word].append(current_word) else: # 注意在反向搜索中next_word实际上是current_word的前驱从end角度看 # 但pre_end记录的是“谁指向当前词”所以关系是 current_word - next_word # 为了统一我们在合并时处理 pre_map[current_word].append(next_word) # 如果next_word在本方向未被访问过 if next_word not in level_map: level_map[next_word] current_level 1 pre_map[next_word].append(current_word) visited_this_level.add(next_word) # 如果next_word在本方向同一层被访问过允许同层多前驱 elif level_map[next_word] current_level 1: pre_map[next_word].append(current_word) # 将本层新发现的单词加入队列 for word in visited_this_level: queue.append(word) # 如果找到相遇点提前终止BFS if found: break # 如果未找到路径 if not found: return [] # 合并两个方向的前驱图构建统一的前驱映射 # 我们需要一个从每个节点到其所有前驱从begin方向看的映射 pre_map_unified defaultdict(list) # 从相遇点开始分别向两端BFS/DFS收集前驱这里我们用DFS简化 # 首先将两个方向的前驱数组合并注意方向性 # pre_begin 记录的是 子节点 - [父节点列表] (从begin出发) # pre_end 记录的是 父节点 - [子节点列表] (从end出发但我们需要将其视为 子节点 - 父节点) # 所以对于pre_end我们需要反转关系 # 合并begin方向的前驱已经是正确的方向 for node, pres in pre_begin.items(): pre_map_unified[node].extend(pres) # 处理end方向的前驱需要反转边 # pre_end 存储的是 word - [next_words]其中next_words是更靠近end的单词 # 从end方向看word的前驱是next_words。所以我们需要建立 next_word - word 的关系 for node, next_words in pre_end.items(): for next_word in next_words: pre_map_unified[next_word].append(node) # 第四步DFS回溯所有路径 (与单向BFS相同) result [] def dfs_backtrack(node: str, path: List[str]): if node beginWord: result.append(path[::-1]) return for pre_node in pre_map_unified.get(node, []): path.append(pre_node) dfs_backtrack(pre_node, path) path.pop() dfs_backtrack(endWord, [endWord]) return result # 测试代码 if __name__ __main__: sol Solution() beginWord hit endWord cog wordList [hot,dot,dog,lot,log,cog] print(双向BFS结果:, sol.findLadders(beginWord, endWord, wordList))双向BFS实现要点两个队列和两个映射分别维护从起点开始queue_begin,level_begin,pre_begin和从终点开始queue_end,level_end,pre_end的搜索状态。扩展策略每次选择当前待扩展节点数较少的一边进行扩展。这是一种常见的优化能平衡两边的搜索进度更快相遇。相遇判断在扩展当前方向的节点current_word时如果发现其邻居next_word已经在另一个方向的level_map中说明两个搜索相遇了。此时next_word或current_word就是相遇点。前驱记录的方向性这是双向BFS最容易出错的地方。pre_begin记录的是从起点方向看的前驱关系父节点-子节点。pre_end记录的是从终点方向看的“后继”关系对于终点方向搜索current_word的后继next_word实际上是更靠近终点的词。在最后合并时需要将pre_end中的关系反转才能与pre_begin统一成从子节点到父节点的映射。提前终止一旦检测到相遇found True就可以跳出BFS循环因为已经找到了最短路径层级的所有必要信息。双向BFS的代码比单向BFS复杂但在处理大规模字典时性能提升非常明显。5. 常见问题与调试技巧即使理解了算法实现时也可能遇到各种问题。下面列出一些常见陷阱和解决方法。问题现象可能原因解决方案与排查思路输出结果为空列表[]1.endWord不在wordList中。2. BFS无法从beginWord到达endWord图不连通。3.pre_map构建错误导致DFS回溯找不到路径。1. 首先检查输入确保endWord in wordList。2. 在BFS循环后打印found变量看是否为True。3. 打印pre_map的内容检查从endWord是否能通过前驱关系链回溯到beginWord。输出结果缺少某些合法最短路径1. 在BFS中同一层发现同一个节点时没有记录所有前驱。2. 使用了visited集合并在发现节点时立即标记导致同层其他前驱被忽略。1.确保使用level_map和visited_this_level模式。判断条件应为if next_word not in level_map新节点或level_map[next_word] current_level 1同层其他前驱。2. 同一层的节点必须全部处理完后再统一标记为已访问加入level_map。程序运行超时 (Time Limit Exceeded)1. 字典wordList很大且使用list的in操作O(N)查找邻居。2. 生成邻居的方式是O(L*26*N)的暴力枚举。3. 图分支很多单向BFS搜索空间爆炸。1.将wordList转换为set使查找操作降为O(1)。2.使用“通配符字典”pattern_dict来高效查找邻居复杂度约为O(L^2)。3.考虑使用双向BFS大幅减少搜索层级。递归深度过深导致栈溢出1. 最短路径可能很长虽然题目有限制但字典大时可能。2. DFS回溯实现有误陷入循环。1. Python默认递归深度约1000对于本题通常足够。如果超出可改用迭代回溯或使用sys.setrecursionlimit提高限制。2. 确保pre_map中不存在环正确BFS构建的图是DAG不会出现环。双向BFS结果错误或漏路径1. 相遇点处理逻辑错误。2. 前驱关系合并错误特别是pre_end的方向反转问题。3. 在找到相遇点后没有继续收集完本层所有可能的前驱关系就停止了。1. 仔细检查相遇条件if next_word in other_level_map。2. 打印pre_begin和pre_end进行对比。记住最终pre_map_unified需要是子节点 - [父节点列表]的映射。3. 找到相遇点后仍需完成本层所有节点的扩展因为本层其他节点也可能通过其他路径与对面相连。代码中应在处理完本层所有节点后再判断found。调试建议使用小例子用题目给的示例或者更简单的例子如hot-dog, [hot,dog,dot]来调试。打印中间状态在BFS每层结束后打印queue,level_map,pre_map的内容观察搜索如何推进以及前驱如何建立。可视化对于简单的例子可以手工画出单词转换图与程序构建的pre_map进行比对。6. 算法优化与最佳实践在掌握了基础解法后我们可以从工程和算法角度思考如何做得更好。6.1 空间与时间的权衡通配符字典的预计算这是用空间换时间的典型。预计算pattern_dict需要O(N*L)的额外空间N为字典大小L为单词长度但将邻居查找从O(L*26*N)降到了O(L^2)。对于一次性求解这个开销通常是值得的。pre_map的存储在最坏情况下如完全图pre_map可能存储O(N^2)条边但实际单词接龙的图通常稀疏。这是找出所有路径必须付出的空间代价。6.2 双向BFS的细节优化平衡扩展如前所述每次扩展节点数较少的一边这是双向BFS的标准优化。提前终止的时机有些实现会在相遇时立即终止。更严谨的做法是完成当前层的全部扩展后再终止因为同一层可能有多条路径在多个点相遇。我们的代码在for _ in range(level_size):循环结束后才检查found保证了本层信息的完整性。合并图的优化我们实现中合并pre_begin和pre_end后进行了完整的DFS。另一种思路是从相遇点分别向起点和终点进行DFS然后将两段路径组合。这可能会减少一些递归深度。6.3 代码可读性与维护性函数拆分将BFS建图和DFS回溯拆分成独立的函数或方法使主函数结构更清晰。使用类型注解如示例代码中的- List[List[str]]这能提高代码的可读性和IDE的提示能力。清晰的变量名使用level_map,pre_map,found,visited_this_level等有意义的名称而不是简单的dist,prev,flag。6.4 应对极端情况起点等于终点虽然题目可能不会这样考但健壮的代码应该处理。如果beginWord endWord直接返回[[beginWord]]。超大字典如果字典非常大如数万单词内存可能成为瓶颈。此时需评估pattern_dict的大小。另一种邻居查找方法是遍历当前单词的每个位置生成25种变化然后在word_set中查找。虽然单次查找慢但避免了预计算的大内存开销是一种空间换时间的反向选择。无解情况尽早判断并返回空列表避免无谓的搜索。7. 总结与扩展通过本文的详细拆解我们掌握了解决LeetCode 126“单词接龙II”的完整思路问题本质在无权图中寻找两点间所有最短路径。这需要BFS来保证“最短”同时记录所有前驱来找到“所有”。核心算法BFS建图 DFS回溯。BFS按层遍历用level_map记录层级用pre_map记录所有前驱。DFS利用pre_map从终点回溯到起点生成所有路径。关键技巧通配符字典高效查找邻居单词。层序处理同一层所有节点处理完后再标记访问以记录同一层的多个前驱。双向BFS从起点和终点同时搜索相遇时停止大幅提升效率。易错点访问标记的时机、前驱记录的逻辑尤其在双向BFS中方向的处理、DFS回溯时路径的反转。扩展思考如果只求一条最短路径这就是LeetCode 127题。可以使用更简单的BFS不需要记录pre_map找到终点立即返回层级。如果要求按字典序输出路径在DFS回溯后对result列表进行排序即可。更通用的图算法本题可以抽象为在无向无权图中找所有最短路径。该算法具有一定的通用性。解决这类问题最重要的是理解BFS层序遍历的特性与记录前驱的必要性并小心处理状态转移和去重。希望这篇教程能帮助你彻底攻克这个经典难题。
在算法面试和日常刷题中单词接龙IILeetCode 126以其复杂的图论建模和路径搜索要求常常让许多开发者感到棘手。它不仅要求找到最短转换序列的长度更要求找出所有可能的最短转换序列这从“单一路径”问题升级为了“全路径”问题对算法的设计和实现都提出了更高要求。本文将围绕Python版本从问题本质出发一步步拆解BFS广度优先搜索结合DFS深度优先搜索或BFS建图再回溯的经典解法并提供完整、可运行的代码示例。无论你是正在准备面试还是希望深入理解图搜索算法这篇文章都将为你提供一套从理解到实现的完整方案。1. 问题核心与难点剖析在深入代码之前我们必须彻底理解题目在问什么以及它为什么难。问题重述LeetCode 126. 单词接龙 II 给定一个起始单词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]] 解释存在两个最短转换序列。核心难点解析找全最短路径而非一条这是与单词接龙I127题最本质的区别。127题只需求最短路径长度通常用BFS一层层遍历找到终点即可终止。而126题要求找出所有最短路径这意味着我们需要记录下所有能到达某个单词的上一层单词前驱节点以便最后能回溯出所有路径。图的结构复杂单词作为节点如果两个单词仅一个字母不同则它们之间有一条无向边。对于一个长度为L的单词它有L25种可能的单字母变换26个字母去掉自身。如果对每个单词都尝试所有可能变换并在字典中查找复杂度是O(L25*N)其中N是字典大小。如何高效地构建或遍历这个隐式图是关键。去重与剪枝在寻找所有路径时同一个单词可能在同层或不同层被多次访问。我们需要一种机制来记录每个单词是在哪一层被发现的并且只接受在同一层或更早层的前驱关系以避免路径绕圈或丢失有效路径。内存与效率的平衡存储所有前驱关系word - List[pre_word]会消耗额外空间。在BFS过程中是每层遍历完再统一记录前驱还是边遍历边记录需要仔细设计以避免逻辑错误。理解了这些难点我们就能有的放矢地设计解决方案。接下来我们将从最直观但低效的方法开始逐步优化到标准的双向BFS建图DFS回溯解法。2. 环境准备与算法思路总览在编写代码前确保你的环境已就绪并对整体算法流程有一个清晰的蓝图。开发环境建议Python版本 3.6及以上。本文代码使用Python标准库不依赖第三方包。IDE或编辑器 任何你熟悉的即可如PyCharm、VSCode、Jupyter Notebook。重点 理解算法思想比运行环境更重要。算法思路总览分层BFS建图 DFS回溯 这是解决本题最经典和高效的方法。整个过程分为两个主要阶段BFS建图阶段目标从beginWord出发进行广度优先搜索直到遇到endWord。在这个过程中不仅要找到终点还要记录下每个单词是由哪些上一层的单词转换而来的即前驱节点列表。关键数据结构queue: 用于BFS的队列。found: 布尔标志记录是否已找到endWord。level_map: 字典记录每个单词首次被发现时的层级从beginWord开始的步数。pre_map: 字典记录每个单词的所有前驱节点即哪些单词可以一步转换到它。这是后续回溯出所有路径的核心。核心策略BFS按层遍历。对于当前层的每个单词生成其所有可能的“下一个单词”如果下一个单词有效在wordList中且满足访问条件则建立从前驱到它的关系。一层遍历完成后再将本层新发现的单词加入已访问集合这是确保能记录同一层多个前驱的关键。DFS回溯阶段目标利用BFS阶段构建好的pre_map从endWord开始深度优先地回溯到beginWord从而构造出所有最短转换序列。过程这是一个标准的递归DFS。从endWord开始查找它的所有前驱单词然后递归地对每个前驱单词做同样的操作直到回溯到beginWord。将路径反转即得到一条从 begin 到 end 的序列。优化由于pre_map是在找到最短路径的前提下构建的所以回溯出的所有路径长度必然相等且最短。此外还有双向BFS的优化变种从起点和终点同时开始搜索相遇时停止可以显著减少搜索空间提升效率。我们会在基础解法之后详细讨论。下面让我们进入核心的代码实现环节。3. 基础解法单向BFS建图 DFS回溯我们先实现最直接的单向BFS方法。虽然它不是最优的但逻辑清晰是理解问题的基础。3.1 辅助函数生成邻接单词在BFS中我们需要频繁地获取一个单词的所有可能“下一跳”。最直接的方法是遍历单词的每个位置将其替换为其他25个字母检查是否在字典中。但更高效的方法是使用“通配符”预处理字典。from collections import defaultdict, deque from typing import List class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) - List[List[str]]: # 第一步预处理构建通配符字典 if endWord not in wordList: return [] word_set set(wordList) # 转换为集合实现O(1)查找 word_set.add(beginWord) # 将起始词也加入方便统一处理 # 构建模式到单词列表的映射例如 h*t - [hot, hit] pattern_dict defaultdict(list) word_len len(beginWord) for word in word_set: for i in range(word_len): pattern word[:i] * word[i1:] pattern_dict[pattern].append(word) # 第二步BFS建图 # level_map 记录单词和其所在的层级距离beginWord的步数 level_map {beginWord: 0} # pre_map 记录单词的所有前驱节点 pre_map defaultdict(list) queue deque([beginWord]) found False level 0 while queue and not found: level_size len(queue) level 1 # 本层新访问的单词用于本层遍历完后统一标记已访问 visited_this_level set() for _ in range(level_size): current_word queue.popleft() # 生成当前单词的所有可能模式并获取邻接词 for i in range(word_len): pattern current_word[:i] * current_word[i1:] for next_word in pattern_dict[pattern]: if next_word current_word: continue # 如果next_word未被访问过或者在本层被访问允许同层多前驱 if next_word not in level_map: level_map[next_word] level pre_map[next_word].append(current_word) visited_this_level.add(next_word) # 如果next_word在当前层被访问过说明是同一层的其他节点也找到了它 elif level_map[next_word] level: pre_map[next_word].append(current_word) if next_word endWord: found True # 将本层新发现的单词加入队列用于下一层扩展 for word in visited_this_level: queue.append(word) # 如果未找到终点返回空列表 if not found: return [] # 第三步DFS回溯所有路径 result [] def dfs_backtrack(node: str, path: List[str]): 从当前节点回溯到起点 if node beginWord: # 找到一条完整路径注意路径是反向的需要反转 result.append(path[::-1]) return # 遍历当前节点的所有前驱 for pre_node in pre_map[node]: path.append(pre_node) dfs_backtrack(pre_node, path) path.pop() # 回溯 # 从终点开始回溯 dfs_backtrack(endWord, [endWord]) return result # 测试代码 if __name__ __main__: sol Solution() beginWord hit endWord cog wordList [hot,dot,dog,lot,log,cog] print(sol.findLadders(beginWord, endWord, wordList)) # 预期输出: [[hit, hot, dot, dog, cog], [hit, hot, lot, log, cog]]代码关键点解释pattern_dict通配符字典这是优化邻接查找的关键。对于单词hot它会生成模式*ot,h*t,ho*。所有能匹配h*t的单词如hot,hit都被认为是相邻的。这样查找一个单词的所有邻居时间复杂度降为O(L^2)L为单词长度因为生成L个模式每个模式可能对应多个单词但平均来看比O(L*26*N)快得多。level_map与visited_this_levellevel_map记录每个单词首次被发现的层级步数。它的作用是判断一个邻居单词是否被访问过以及是否是在同一层被访问的。visited_this_level是一个临时集合用于收集本层BFS新发现的所有单词。为什么不能发现一个就立刻加入queue并标记已访问因为如果立刻标记那么同一层中其他节点可能就无法再访问这个单词从而丢失一条有效的最短路径。例如A和B在同一层都能到达C。如果A先发现C并标记B就无法记录C为邻居了。因此必须等一层全部处理完再统一将这些新单词入队并记录层级。pre_map的构建逻辑if next_word not in level_map:表示第一次发现该单词记录其层级并建立前驱关系。elif level_map[next_word] level:表示该单词在本层已经被其他节点发现过这是另一条最短路径的前驱因此需要将当前节点也加入其前驱列表。DFS回溯从endWord开始递归地查找pre_map中的前驱直到beginWord。由于我们是从终点向起点回溯所以得到的路径是反向的最后需要反转。使用path.append()和path.pop()实现标准的回溯算法。这个解法在逻辑上是正确的但对于某些极端用例单词很长、字典很大单向BFS的搜索空间可能依然很大。接下来我们看如何用双向BFS进行优化。4. 高效解法双向BFS建图 DFS回溯双向BFS的核心思想是同时从起点和终点开始搜索当两边的搜索相遇时停止。这能极大地减少搜索的层级和需要探索的节点数量尤其当分支因子较大时效果显著。双向BFS建图的特殊之处 我们需要维护两个方向的层级映射和前驱映射。当从起点方向发现一个单词已被终点方向访问过或反之即表示“相遇”找到了最短路径。此时我们需要合并两个方向的前驱信息以构建完整的pre_map。下面是双向BFS的实现代码from collections import defaultdict, deque from typing import List class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) - List[List[str]]: if endWord not in wordList: return [] word_set set(wordList) # 将起始词加入字典方便模式匹配 if beginWord not in word_set: word_set.add(beginWord) # 构建通配符字典 word_len len(beginWord) pattern_dict defaultdict(list) for word in word_set: for i in range(word_len): pattern word[:i] * word[i1:] pattern_dict[pattern].append(word) # 双向BFS初始化 # 层级记录从起点开始的距离 / 从终点开始的距离 level_begin {beginWord: 0} level_end {endWord: 0} # 前驱记录 pre_begin defaultdict(list) # key: word, value: list of previous words from begin side pre_end defaultdict(list) # key: word, value: list of next words from end side (注意方向) queue_begin deque([beginWord]) queue_end deque([endWord]) found False meet_node None forward True # 搜索方向标志True表示从begin向end搜索 while queue_begin and queue_end and not found: # 每次选择节点数较少的一边进行扩展优化搜索效率 if len(queue_begin) len(queue_end): queue, level_map, other_level_map, pre_map, forward queue_begin, level_begin, level_end, pre_begin, True else: queue, level_map, other_level_map, pre_map, forward queue_end, level_end, level_begin, pre_end, False level_size len(queue) visited_this_level set() for _ in range(level_size): current_word queue.popleft() current_level level_map[current_word] for i in range(word_len): pattern current_word[:i] * current_word[i1:] for next_word in pattern_dict[pattern]: if next_word current_word: continue # 关键判断相遇条件 if next_word in other_level_map: # 找到相遇点 found True meet_node next_word # 根据方向建立前驱关系 if forward: pre_map[next_word].append(current_word) else: # 注意在反向搜索中next_word实际上是current_word的前驱从end角度看 # 但pre_end记录的是“谁指向当前词”所以关系是 current_word - next_word # 为了统一我们在合并时处理 pre_map[current_word].append(next_word) # 如果next_word在本方向未被访问过 if next_word not in level_map: level_map[next_word] current_level 1 pre_map[next_word].append(current_word) visited_this_level.add(next_word) # 如果next_word在本方向同一层被访问过允许同层多前驱 elif level_map[next_word] current_level 1: pre_map[next_word].append(current_word) # 将本层新发现的单词加入队列 for word in visited_this_level: queue.append(word) # 如果找到相遇点提前终止BFS if found: break # 如果未找到路径 if not found: return [] # 合并两个方向的前驱图构建统一的前驱映射 # 我们需要一个从每个节点到其所有前驱从begin方向看的映射 pre_map_unified defaultdict(list) # 从相遇点开始分别向两端BFS/DFS收集前驱这里我们用DFS简化 # 首先将两个方向的前驱数组合并注意方向性 # pre_begin 记录的是 子节点 - [父节点列表] (从begin出发) # pre_end 记录的是 父节点 - [子节点列表] (从end出发但我们需要将其视为 子节点 - 父节点) # 所以对于pre_end我们需要反转关系 # 合并begin方向的前驱已经是正确的方向 for node, pres in pre_begin.items(): pre_map_unified[node].extend(pres) # 处理end方向的前驱需要反转边 # pre_end 存储的是 word - [next_words]其中next_words是更靠近end的单词 # 从end方向看word的前驱是next_words。所以我们需要建立 next_word - word 的关系 for node, next_words in pre_end.items(): for next_word in next_words: pre_map_unified[next_word].append(node) # 第四步DFS回溯所有路径 (与单向BFS相同) result [] def dfs_backtrack(node: str, path: List[str]): if node beginWord: result.append(path[::-1]) return for pre_node in pre_map_unified.get(node, []): path.append(pre_node) dfs_backtrack(pre_node, path) path.pop() dfs_backtrack(endWord, [endWord]) return result # 测试代码 if __name__ __main__: sol Solution() beginWord hit endWord cog wordList [hot,dot,dog,lot,log,cog] print(双向BFS结果:, sol.findLadders(beginWord, endWord, wordList))双向BFS实现要点两个队列和两个映射分别维护从起点开始queue_begin,level_begin,pre_begin和从终点开始queue_end,level_end,pre_end的搜索状态。扩展策略每次选择当前待扩展节点数较少的一边进行扩展。这是一种常见的优化能平衡两边的搜索进度更快相遇。相遇判断在扩展当前方向的节点current_word时如果发现其邻居next_word已经在另一个方向的level_map中说明两个搜索相遇了。此时next_word或current_word就是相遇点。前驱记录的方向性这是双向BFS最容易出错的地方。pre_begin记录的是从起点方向看的前驱关系父节点-子节点。pre_end记录的是从终点方向看的“后继”关系对于终点方向搜索current_word的后继next_word实际上是更靠近终点的词。在最后合并时需要将pre_end中的关系反转才能与pre_begin统一成从子节点到父节点的映射。提前终止一旦检测到相遇found True就可以跳出BFS循环因为已经找到了最短路径层级的所有必要信息。双向BFS的代码比单向BFS复杂但在处理大规模字典时性能提升非常明显。5. 常见问题与调试技巧即使理解了算法实现时也可能遇到各种问题。下面列出一些常见陷阱和解决方法。问题现象可能原因解决方案与排查思路输出结果为空列表[]1.endWord不在wordList中。2. BFS无法从beginWord到达endWord图不连通。3.pre_map构建错误导致DFS回溯找不到路径。1. 首先检查输入确保endWord in wordList。2. 在BFS循环后打印found变量看是否为True。3. 打印pre_map的内容检查从endWord是否能通过前驱关系链回溯到beginWord。输出结果缺少某些合法最短路径1. 在BFS中同一层发现同一个节点时没有记录所有前驱。2. 使用了visited集合并在发现节点时立即标记导致同层其他前驱被忽略。1.确保使用level_map和visited_this_level模式。判断条件应为if next_word not in level_map新节点或level_map[next_word] current_level 1同层其他前驱。2. 同一层的节点必须全部处理完后再统一标记为已访问加入level_map。程序运行超时 (Time Limit Exceeded)1. 字典wordList很大且使用list的in操作O(N)查找邻居。2. 生成邻居的方式是O(L*26*N)的暴力枚举。3. 图分支很多单向BFS搜索空间爆炸。1.将wordList转换为set使查找操作降为O(1)。2.使用“通配符字典”pattern_dict来高效查找邻居复杂度约为O(L^2)。3.考虑使用双向BFS大幅减少搜索层级。递归深度过深导致栈溢出1. 最短路径可能很长虽然题目有限制但字典大时可能。2. DFS回溯实现有误陷入循环。1. Python默认递归深度约1000对于本题通常足够。如果超出可改用迭代回溯或使用sys.setrecursionlimit提高限制。2. 确保pre_map中不存在环正确BFS构建的图是DAG不会出现环。双向BFS结果错误或漏路径1. 相遇点处理逻辑错误。2. 前驱关系合并错误特别是pre_end的方向反转问题。3. 在找到相遇点后没有继续收集完本层所有可能的前驱关系就停止了。1. 仔细检查相遇条件if next_word in other_level_map。2. 打印pre_begin和pre_end进行对比。记住最终pre_map_unified需要是子节点 - [父节点列表]的映射。3. 找到相遇点后仍需完成本层所有节点的扩展因为本层其他节点也可能通过其他路径与对面相连。代码中应在处理完本层所有节点后再判断found。调试建议使用小例子用题目给的示例或者更简单的例子如hot-dog, [hot,dog,dot]来调试。打印中间状态在BFS每层结束后打印queue,level_map,pre_map的内容观察搜索如何推进以及前驱如何建立。可视化对于简单的例子可以手工画出单词转换图与程序构建的pre_map进行比对。6. 算法优化与最佳实践在掌握了基础解法后我们可以从工程和算法角度思考如何做得更好。6.1 空间与时间的权衡通配符字典的预计算这是用空间换时间的典型。预计算pattern_dict需要O(N*L)的额外空间N为字典大小L为单词长度但将邻居查找从O(L*26*N)降到了O(L^2)。对于一次性求解这个开销通常是值得的。pre_map的存储在最坏情况下如完全图pre_map可能存储O(N^2)条边但实际单词接龙的图通常稀疏。这是找出所有路径必须付出的空间代价。6.2 双向BFS的细节优化平衡扩展如前所述每次扩展节点数较少的一边这是双向BFS的标准优化。提前终止的时机有些实现会在相遇时立即终止。更严谨的做法是完成当前层的全部扩展后再终止因为同一层可能有多条路径在多个点相遇。我们的代码在for _ in range(level_size):循环结束后才检查found保证了本层信息的完整性。合并图的优化我们实现中合并pre_begin和pre_end后进行了完整的DFS。另一种思路是从相遇点分别向起点和终点进行DFS然后将两段路径组合。这可能会减少一些递归深度。6.3 代码可读性与维护性函数拆分将BFS建图和DFS回溯拆分成独立的函数或方法使主函数结构更清晰。使用类型注解如示例代码中的- List[List[str]]这能提高代码的可读性和IDE的提示能力。清晰的变量名使用level_map,pre_map,found,visited_this_level等有意义的名称而不是简单的dist,prev,flag。6.4 应对极端情况起点等于终点虽然题目可能不会这样考但健壮的代码应该处理。如果beginWord endWord直接返回[[beginWord]]。超大字典如果字典非常大如数万单词内存可能成为瓶颈。此时需评估pattern_dict的大小。另一种邻居查找方法是遍历当前单词的每个位置生成25种变化然后在word_set中查找。虽然单次查找慢但避免了预计算的大内存开销是一种空间换时间的反向选择。无解情况尽早判断并返回空列表避免无谓的搜索。7. 总结与扩展通过本文的详细拆解我们掌握了解决LeetCode 126“单词接龙II”的完整思路问题本质在无权图中寻找两点间所有最短路径。这需要BFS来保证“最短”同时记录所有前驱来找到“所有”。核心算法BFS建图 DFS回溯。BFS按层遍历用level_map记录层级用pre_map记录所有前驱。DFS利用pre_map从终点回溯到起点生成所有路径。关键技巧通配符字典高效查找邻居单词。层序处理同一层所有节点处理完后再标记访问以记录同一层的多个前驱。双向BFS从起点和终点同时搜索相遇时停止大幅提升效率。易错点访问标记的时机、前驱记录的逻辑尤其在双向BFS中方向的处理、DFS回溯时路径的反转。扩展思考如果只求一条最短路径这就是LeetCode 127题。可以使用更简单的BFS不需要记录pre_map找到终点立即返回层级。如果要求按字典序输出路径在DFS回溯后对result列表进行排序即可。更通用的图算法本题可以抽象为在无向无权图中找所有最短路径。该算法具有一定的通用性。解决这类问题最重要的是理解BFS层序遍历的特性与记录前驱的必要性并小心处理状态转移和去重。希望这篇教程能帮助你彻底攻克这个经典难题。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
