企业官网建设流程全解析

在算法面试和日常刷题中，单词接龙II（LeetCode 126）以其复杂的图论建模和路径搜索要求，常常让许多开发者感到棘手。它不仅要求找到最短转换序列的长度，更要求找出所有可能的最短转换序列，这从“单一路径”问题升级为了“全路径”问题，对算法的设计和实现都提出了更高要求。本文将围绕Python版本，从问题本质出发，一步步拆解BFS（广度优先搜索）结合DFS（深度优先搜索）或BFS建图再回溯的经典解法，并提供完整、可运行的代码示例。无论你是正在准备面试，还是希望深入理解图搜索算法，这篇文章都将为你提供一套从理解到实现的完整方案。

1. 问题核心与难点剖析

在深入代码之前，我们必须彻底理解题目在问什么，以及它为什么难。

问题重述（LeetCode 126. 单词接龙 II）： 给定一个起始单词beginWord、一个结束单词endWord和一个字典wordList。需要找出所有从beginWord到endWord的最短转换序列，并返回这些序列列表。转换需遵循以下规则：

1. 每次转换只能改变一个字母。
2. 转换过程中的每个中间单词必须是字典wordList中的单词（注意：beginWord不需要在字典中，但endWord必须在字典中）。

示例：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 输出：[["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"]] 解释：存在两个最短转换序列。

核心难点解析：

1. 找全最短路径，而非一条：这是与单词接龙I（127题）最本质的区别。127题只需求最短路径长度，通常用BFS一层层遍历，找到终点即可终止。而126题要求找出所有最短路径，这意味着我们需要记录下所有能到达某个单词的上一层单词（前驱节点），以便最后能回溯出所有路径。
2. 图的结构复杂：单词作为节点，如果两个单词仅一个字母不同，则它们之间有一条无向边。对于一个长度为L的单词，它有L25种可能的单字母变换（26个字母去掉自身）。如果对每个单词都尝试所有可能变换并在字典中查找，复杂度是O(L25*N)，其中N是字典大小。如何高效地构建或遍历这个隐式图是关键。
3. 去重与剪枝：在寻找所有路径时，同一个单词可能在同层或不同层被多次访问。我们需要一种机制来记录每个单词是在哪一层被发现的，并且只接受在同一层或更早层的前驱关系，以避免路径绕圈或丢失有效路径。
4. 内存与效率的平衡：存储所有前驱关系（word -> List[pre_word]）会消耗额外空间。在BFS过程中，是每层遍历完再统一记录前驱，还是边遍历边记录，需要仔细设计以避免逻辑错误。

理解了这些难点，我们就能有的放矢地设计解决方案。接下来，我们将从最直观但低效的方法开始，逐步优化到标准的双向BFS建图+DFS回溯解法。

2. 环境准备与算法思路总览

在编写代码前，确保你的环境已就绪，并对整体算法流程有一个清晰的蓝图。

开发环境建议：

• Python版本： 3.6及以上。本文代码使用Python标准库，不依赖第三方包。
• IDE或编辑器： 任何你熟悉的即可，如PyCharm、VSCode、Jupyter Notebook。
• 重点： 理解算法思想比运行环境更重要。

算法思路总览（分层BFS建图 + DFS回溯）： 这是解决本题最经典和高效的方法。整个过程分为两个主要阶段：

1. BFS建图阶段：

   • 目标：从beginWord出发，进行广度优先搜索，直到遇到endWord。在这个过程中，不仅要找到终点，还要记录下每个单词是由哪些上一层的单词转换而来的（即前驱节点列表）。
   • 关键数据结构：
     • queue: 用于BFS的队列。
     • found: 布尔标志，记录是否已找到endWord。
     • level_map: 字典，记录每个单词首次被发现时的层级（从beginWord开始的步数）。
     • pre_map: 字典，记录每个单词的所有前驱节点（即哪些单词可以一步转换到它）。这是后续回溯出所有路径的核心。
   • 核心策略：BFS按层遍历。对于当前层的每个单词，生成其所有可能的“下一个单词”，如果下一个单词有效（在wordList中且满足访问条件），则建立从前驱到它的关系。一层遍历完成后，再将本层新发现的单词加入已访问集合，这是确保能记录同一层多个前驱的关键。

2. 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[i+1:] 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[i+1:] 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']]

代码关键点解释：

1. pattern_dict（通配符字典）：这是优化邻接查找的关键。对于单词"hot"，它会生成模式"*ot","h*t","ho*"。所有能匹配"h*t"的单词（如"hot","hit"）都被认为是相邻的。这样，查找一个单词的所有邻居时间复杂度降为O(L^2)（L为单词长度），因为生成L个模式，每个模式可能对应多个单词，但平均来看比O(L*26*N)快得多。
2. level_map与visited_this_level：
   • level_map记录每个单词首次被发现的层级（步数）。它的作用是判断一个邻居单词是否被访问过，以及是否是在同一层被访问的。
   • visited_this_level是一个临时集合，用于收集本层BFS新发现的所有单词。为什么不能发现一个就立刻加入queue并标记已访问？因为如果立刻标记，那么同一层中其他节点可能就无法再访问这个单词，从而丢失一条有效的最短路径。例如，A和B在同一层，都能到达C。如果A先发现C并标记，B就无法记录C为邻居了。因此，必须等一层全部处理完，再统一将这些新单词入队并记录层级。
3. pre_map的构建逻辑：
   • if next_word not in level_map:：表示第一次发现该单词，记录其层级，并建立前驱关系。
   • elif level_map[next_word] == level:：表示该单词在本层已经被其他节点发现过，这是另一条最短路径的前驱，因此需要将当前节点也加入其前驱列表。
4. 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[i+1:] 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[i+1:] 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实现要点：

1. 两个队列和两个映射：分别维护从起点开始（queue_begin,level_begin,pre_begin）和从终点开始（queue_end,level_end,pre_end）的搜索状态。
2. 扩展策略：每次选择当前待扩展节点数较少的一边进行扩展。这是一种常见的优化，能平衡两边的搜索进度，更快相遇。
3. 相遇判断：在扩展当前方向的节点current_word时，如果发现其邻居next_word已经在另一个方向的level_map中，说明两个搜索相遇了。此时，next_word（或current_word）就是相遇点。
4. 前驱记录的方向性：这是双向BFS最容易出错的地方。pre_begin记录的是从起点方向看的前驱关系（父节点->子节点）。pre_end记录的是从终点方向看的“后继”关系（对于终点方向搜索，current_word的后继next_word实际上是更靠近终点的词）。在最后合并时，需要将pre_end中的关系反转，才能与pre_begin统一成从子节点到父节点的映射。
5. 提前终止：一旦检测到相遇（found = True），就可以跳出BFS循环，因为已经找到了最短路径层级的所有必要信息。

双向BFS的代码比单向BFS复杂，但在处理大规模字典时，性能提升非常明显。

5. 常见问题与调试技巧

即使理解了算法，实现时也可能遇到各种问题。下面列出一些常见陷阱和解决方法。

调试建议：

1. 使用小例子：用题目给的示例，或者更简单的例子（如"hot"->"dog", ["hot","dog","dot"]）来调试。
2. 打印中间状态：在BFS每层结束后，打印queue,level_map,pre_map的内容，观察搜索如何推进以及前驱如何建立。
3. 可视化：对于简单的例子，可以手工画出单词转换图，与程序构建的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”的完整思路：

1. 问题本质：在无权图中寻找两点间所有最短路径。这需要BFS来保证“最短”，同时记录所有前驱来找到“所有”。
2. 核心算法：BFS建图 + DFS回溯。BFS按层遍历，用level_map记录层级，用pre_map记录所有前驱。DFS利用pre_map从终点回溯到起点，生成所有路径。
3. 关键技巧：
   • 通配符字典：高效查找邻居单词。
   • 层序处理：同一层所有节点处理完后再标记访问，以记录同一层的多个前驱。
   • 双向BFS：从起点和终点同时搜索，相遇时停止，大幅提升效率。
4. 易错点：访问标记的时机、前驱记录的逻辑（尤其在双向BFS中方向的处理）、DFS回溯时路径的反转。

扩展思考：

• 如果只求一条最短路径：这就是LeetCode 127题。可以使用更简单的BFS，不需要记录pre_map，找到终点立即返回层级。
• 如果要求按字典序输出路径：在DFS回溯后，对result列表进行排序即可。
• 更通用的图算法：本题可以抽象为在无向无权图中找所有最短路径。该算法具有一定的通用性。

解决这类问题，最重要的是理解BFS层序遍历的特性与记录前驱的必要性，并小心处理状态转移和去重。希望这篇教程能帮助你彻底攻克这个经典难题。