LeetCode 126. 单词接龙 II

字数 3689 2025-10-26 19:15:22

LeetCode 126. 单词接龙 II

题目描述
给定一个起始单词 beginWord、一个结束单词 endWord 和一个单词列表 wordList。你需要找出所有从 beginWord 到 endWord 的最短转换序列。转换序列需要遵循以下规则：

每次转换只能改变一个字母。
转换过程中的每个中间单词都必须是 wordList 中的单词。

注意：

如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
单词列表中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

解题过程

这个问题是 LeetCode 127. 单词接龙的进阶版，127题只需要返回最短路径的长度，而本题需要返回所有可能的最短路径本身。这大大增加了难度，我们需要记录完整的路径信息。

1. 问题分析
我们可以将这个问题建模成一个图论问题：

节点 (Node): 每个单词就是一个节点。
边 (Edge): 如果两个单词之间只有一个字母不同，那么它们之间就存在一条无向边。
目标: 找到从起始节点 (beginWord) 到目标节点 (endWord) 的所有最短路径。

由于需要找出"所有"最短路径，简单的广度优先搜索 (BFS) 只能找到一条最短路径或者其长度。我们需要对 BFS 进行增强。

2. 核心思路：层级 BFS 与邻接表
关键点在于，我们需要知道在 BFS 遍历过程中，每个节点是从哪些上一层节点过来的。这样，当我们到达终点时，就可以通过这些"父节点"信息反向回溯，构建出所有完整的路径。

具体步骤：

构建图结构（隐式）： 我们不会预先构建出整个图，因为单词列表可能很大。取而代之的是，在 BFS 过程中，对于一个给定的单词，我们通过改变它的每一个字母（从 'a' 到 'z'）来生成所有可能的邻居，并检查这个新单词是否存在于 wordList 中。这是一种"按需"生成邻居的方式，效率更高。
层级式 BFS 遍历：
- 我们使用一个队列 (queue) 来进行 BFS。
- 我们使用一个数据结构（通常是字典或哈希表）来记录每个节点的距离（从起点到该节点的步数）以及它的父节点列表（即，有哪些节点在上一层级可以一步到达当前节点）。这个记录父节点列表的结构是本题的核心。
- BFS 是逐层扩展的。我们处理完一层的所有节点后，再一起进入下一层。
回溯构建路径：
- 当 BFS 遍历到 endWord 时，我们并不停止，而是将当前层的所有节点处理完。这是因为可能有多条不同的最短路径在同一时刻到达 endWord。
- 在 BFS 结束后，我们使用深度优先搜索 (DFS) 从 endWord 开始，根据记录好的"父节点列表"反向回溯，直到 beginWord，从而构建出每一条完整的路径。

3. 详细步骤分解

步骤一：预处理

将 wordList 转换为集合 (set)，以便进行 O(1) 时间复杂度的查找。
检查 endWord 是否在 wordList 中，如果不在，直接返回空列表 []，因为不可能有解。

步骤二：初始化 BFS 所需的数据结构

queue: 一个队列，初始时包含 beginWord。
visited: 一个字典，用于记录每个节点在哪一层被访问到。键是单词，值是层级（从起点开始的步数）。初始状态：visited = {beginWord: 0}。
parent_map: 一个字典，用于记录每个节点的父节点列表。键是单词，值是一个集合，包含所有能一步到达该键的单词。初始状态：parent_map = {beginWord: set()} （beginWord 没有父节点）。对于其他节点，我们会在 BFS 过程中动态添加。
found：一个布尔标志，用于标记是否已经找到了 endWord。初始为 False。
level = 0：当前层级。

步骤三：执行层级 BFS

当队列不为空，且我们还没有处理完包含 endWord 的那一层时，继续循环。
记录当前队列的大小 n（即当前层的节点数量）。
初始化一个临时的集合 level_visited，用于记录当前层新访问到的所有节点。为什么需要这个？ 因为同一层的不同节点可能指向下一层的同一个节点。如果我们处理一个节点就把它标记为已访问，那么同一层后面节点生成的相同邻居就会被忽略，从而丢失一条路径。我们必须等一层全部处理完后，再统一标记这些新节点为已访问。
对于队列中的前 n 个节点（当前层的所有节点）：
1. 弹出当前节点 current_word。
2. 生成 current_word 的所有可能的邻居单词。方法是遍历单词的每个位置，将该位置的字母依次替换为 'a' 到 'z'（排除自身），生成新单词 next_word。
3. 对于每个生成的 next_word：
  - 如果 next_word 不在 wordList 中，跳过。
  - 如果 next_word 已经被访问过（即在 visited 字典中），检查其访问层级：
    - 如果 visited[next_word] == level + 1，这说明 next_word 是在下一层被访问的，并且当前节点 current_word 是它的一个父节点。此时，我们需要将 current_word 添加到 parent_map[next_word] 的父节点列表中。
    - 如果 visited[next_word] < level + 1，这说明 next_word 是在更早的层级被访问的，current_word 不是到达它的最短路径上的节点，直接忽略。
  - 如果 next_word 尚未被访问过（即不在 visited 中）:
    - 将 next_word 加入队列（实际上先加入 level_visited）。
    - 在 visited 中记录 visited[next_word] = level + 1。
    - 在 parent_map 中为 next_word 初始化一个父节点集合，并加入 current_word，即 parent_map.setdefault(next_word, set()).add(current_word)。
    - 如果 next_word == endWord，将 found 标志设为 True。注意：此时不退出循环，因为同一层可能还有其他路径到达 endWord。
当前层所有节点处理完毕后，将 level_visited 中的所有节点正式标记为已访问（实际上在第三步的 3.2 中已经加入了 visited，这里主要是为了逻辑清晰）。
层级 level 加 1。
如果 found 为 True，说明我们已经处理完了包含 endWord 的那一层，可以结束 BFS。因为更深的路径一定不是最短路径。

步骤四：通过 DFS 回溯所有路径

初始化一个结果列表 results = []。
从 endWord 开始，进行深度优先搜索 (DFS) 回溯。DFS 的函数参数通常包括 current_word（当前回溯到的单词）和 current_path（当前已构建的路径，初始为 [endWord]）。
在 DFS 函数中：
- 如果 current_word == beginWord，说明找到了一条完整路径。因为 current_path 是从终点开始的，所以需要将其反转，然后加入 results。即 results.append(current_path[::-1])。
- 否则，遍历 current_word 的所有父节点（从 parent_map 中获取）。
- 对于每个父节点 parent，将 parent 加入 current_path，然后递归调用 DFS 函数：dfs(parent, current_path)。
- 递归返回后，将 parent 从 current_path 中移除（回溯）。
调用 DFS 函数：dfs(endWord, [endWord])。
返回 results。

总结
这道题的难点在于将标准的求最短路径长度的 BFS，改造成能记录所有路径信息的"层级 BFS + 父节点映射"，最后再通过 DFS 回溯来构建路径。关键在于：

按层处理，防止同层节点互相覆盖路径。
使用 parent_map 精确记录每个节点的来源。
BFS 找到终点后不立即停止，而是处理完整个层级。
最后通过 DFS 从终点反向回溯至起点，生成所有路径。

LeetCode 126. 单词接龙 II 题目描述给定一个起始单词 beginWord 、一个结束单词 endWord 和一个单词列表 wordList 。你需要找出所有从 beginWord 到 endWord 的最短转换序列。转换序列需要遵循以下规则：每次转换只能改变一个字母。转换过程中的每个中间单词都必须是 wordList 中的单词。注意：如果不存在这样的转换序列，返回一个空列表。所有单词具有相同的长度。所有单词只由小写字母组成。单词列表中不存在重复的单词。你可以假设 beginWord 和 endWord 是非空的，且二者不相同。解题过程这个问题是 LeetCode 127. 单词接龙的进阶版，127题只需要返回最短路径的长度，而本题需要返回所有可能的最短路径本身。这大大增加了难度，我们需要记录完整的路径信息。 1. 问题分析我们可以将这个问题建模成一个图论问题：节点 (Node): 每个单词就是一个节点。边 (Edge): 如果两个单词之间只有一个字母不同，那么它们之间就存在一条无向边。目标: 找到从起始节点 ( beginWord ) 到目标节点 ( endWord ) 的所有最短路径。由于需要找出"所有"最短路径，简单的广度优先搜索 (BFS) 只能找到一条最短路径或者其长度。我们需要对 BFS 进行增强。 2. 核心思路：层级 BFS 与邻接表关键点在于，我们需要知道在 BFS 遍历过程中，每个节点是从哪些上一层节点过来的。这样，当我们到达终点时，就可以通过这些"父节点"信息反向回溯，构建出所有完整的路径。具体步骤：构建图结构（隐式）：我们不会预先构建出整个图，因为单词列表可能很大。取而代之的是，在 BFS 过程中，对于一个给定的单词，我们通过改变它的每一个字母（从 'a' 到 'z'）来生成所有可能的邻居，并检查这个新单词是否存在于 wordList 中。这是一种"按需"生成邻居的方式，效率更高。层级式 BFS 遍历：我们使用一个队列 ( queue ) 来进行 BFS。我们使用一个数据结构（通常是字典或哈希表）来记录每个节点的距离（从起点到该节点的步数）以及它的父节点列表（即，有哪些节点在上一层级可以一步到达当前节点）。这个记录父节点列表的结构是本题的核心。 BFS 是逐层扩展的。我们处理完一层的所有节点后，再一起进入下一层。回溯构建路径：当 BFS 遍历到 endWord 时，我们并不停止，而是将当前层的所有节点处理完。这是因为可能有多条不同的最短路径在同一时刻到达 endWord 。在 BFS 结束后，我们使用深度优先搜索 (DFS) 从 endWord 开始，根据记录好的"父节点列表"反向回溯，直到 beginWord ，从而构建出每一条完整的路径。 3. 详细步骤分解步骤一：预处理将 wordList 转换为集合 ( set )，以便进行 O(1) 时间复杂度的查找。检查 endWord 是否在 wordList 中，如果不在，直接返回空列表 [] ，因为不可能有解。步骤二：初始化 BFS 所需的数据结构 queue : 一个队列，初始时包含 beginWord 。 visited : 一个字典，用于记录每个节点在哪一层被访问到。键是单词，值是层级（从起点开始的步数）。初始状态： visited = {beginWord: 0} 。 parent_map : 一个字典，用于记录每个节点的父节点列表。键是单词，值是一个集合，包含所有能一步到达该键的单词。初始状态： parent_map = {beginWord: set()} （ beginWord 没有父节点）。对于其他节点，我们会在 BFS 过程中动态添加。 found ：一个布尔标志，用于标记是否已经找到了 endWord 。初始为 False 。 level = 0 ：当前层级。步骤三：执行层级 BFS 当队列不为空，且我们还没有处理完包含 endWord 的那一层时，继续循环。记录当前队列的大小 n （即当前层的节点数量）。初始化一个临时的集合 level_visited ，用于记录当前层新访问到的所有节点。为什么需要这个？因为同一层的不同节点可能指向下一层的同一个节点。如果我们处理一个节点就把它标记为已访问，那么同一层后面节点生成的相同邻居就会被忽略，从而丢失一条路径。我们必须等一层全部处理完后，再统一标记这些新节点为已访问。对于队列中的前 n 个节点（当前层的所有节点）：弹出当前节点 current_word 。生成 current_word 的所有可能的邻居单词。方法是遍历单词的每个位置，将该位置的字母依次替换为 'a' 到 'z'（排除自身），生成新单词 next_word 。对于每个生成的 next_word ：如果 next_word 不在 wordList 中，跳过。如果 next_word 已经被访问过（即在 visited 字典中），检查其访问层级：如果 visited[next_word] == level + 1 ，这说明 next_word 是在下一层被访问的，并且当前节点 current_word 是它的一个父节点。此时，我们需要将 current_word 添加到 parent_map[next_word] 的父节点列表中。如果 visited[next_word] < level + 1 ，这说明 next_word 是在更早的层级被访问的， current_word 不是到达它的最短路径上的节点，直接忽略。如果 next_word 尚未被访问过（即不在 visited 中）: 将 next_word 加入队列（实际上先加入 level_visited ）。在 visited 中记录 visited[next_word] = level + 1 。在 parent_map 中为 next_word 初始化一个父节点集合，并加入 current_word ，即 parent_map.setdefault(next_word, set()).add(current_word) 。如果 next_word == endWord ，将 found 标志设为 True 。注意：此时不退出循环，因为同一层可能还有其他路径到达 endWord 。当前层所有节点处理完毕后，将 level_visited 中的所有节点正式标记为已访问（实际上在第三步的 3.2 中已经加入了 visited ，这里主要是为了逻辑清晰）。层级 level 加 1。如果 found 为 True ，说明我们已经处理完了包含 endWord 的那一层，可以结束 BFS。因为更深的路径一定不是最短路径。步骤四：通过 DFS 回溯所有路径初始化一个结果列表 results = [] 。从 endWord 开始，进行深度优先搜索 (DFS) 回溯。DFS 的函数参数通常包括 current_word （当前回溯到的单词）和 current_path （当前已构建的路径，初始为 [endWord] ）。在 DFS 函数中：如果 current_word == beginWord ，说明找到了一条完整路径。因为 current_path 是从终点开始的，所以需要将其反转，然后加入 results 。即 results.append(current_path[::-1]) 。否则，遍历 current_word 的所有父节点（从 parent_map 中获取）。对于每个父节点 parent ，将 parent 加入 current_path ，然后递归调用 DFS 函数： dfs(parent, current_path) 。递归返回后，将 parent 从 current_path 中移除（回溯）。调用 DFS 函数： dfs(endWord, [endWord]) 。返回 results 。总结这道题的难点在于将标准的求最短路径长度的 BFS，改造成能记录所有路径信息的"层级 BFS + 父节点映射"，最后再通过 DFS 回溯来构建路径。关键在于：按层处理，防止同层节点互相覆盖路径。使用 parent_map 精确记录每个节点的来源。 BFS 找到终点后不立即停止，而是处理完整个层级。最后通过 DFS 从终点反向回溯至起点，生成所有路径。