LeetCode 127. 单词接龙 II
字数 2315 2025-12-22 09:05:29

LeetCode 127. 单词接龙 II

题目描述：

给定两个单词 beginWord 和 endWord，以及一个单词列表 wordList。要求找出所有从 beginWord 到 endWord 的最短转换序列，转换需遵循以下规则：

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

返回所有最短转换序列。如果不存在这样的转换序列，返回空列表。每个序列都应包含 beginWord 和 endWord，且序列之间顺序任意。

解题过程循序渐进讲解：

第一步：问题理解与建模
这个问题本质上是在一个图（Graph）中寻找所有最短路径。图的节点是每个单词（包括 beginWord``），如果两个单词之间仅相差一个字母，则它们之间有一条无向边。目标是从起点 beginWord到终点endWord` 的所有最短路径（即转换序列）。

第二步：基础思路——为什么不能简单用BFS？
普通的广度优先搜索（BFS）可以找到一条最短路径，但本题要求找出“所有”最短路径。如果我们在BFS过程中，一旦找到 endWord 就停止，那么只能得到一条路径。而且，简单地记录所有路径可能导致搜索空间爆炸（因为要探索所有可能路径）。因此，我们需要一种能够系统地找出所有最短路径，同时避免指数级复杂度的算法。

第三步：核心算法——双向BFS + 层次化建图
一个高效的解法是结合双向BFS和层次化建图（也叫“广度优先搜索树”或“距离图”）。

  • 双向BFS：同时从 beginWord 和 endWord 开始进行BFS，当两个搜索相遇时，就找到了最短路径长度。这可以减少搜索的节点数量。
  • 层次化建图：在BFS过程中，我们不仅记录每个节点到起点的距离（或层级），还记录每个节点的“父节点列表”（即哪些节点可以一步到达当前节点）。这样，我们在找到所有最短路径后，可以通过回溯从 endWord 到 beginWord 来重建所有路径。

第四步：具体步骤详解

  1. 预处理与检查

    • 将 wordList 转换为集合（Set），便于 O(1) 时间查找。
    • 检查 endWord 是否在集合中，如果不在，直接返回空列表。

  2. 双向BFS构建距离和父节点关系图

    • 使用两个队列分别从起点（beginWord）和终点（endWord）开始BFS。
    • 维护两个距离字典：distanceFromBegin[word] 和 distanceFromEnd[word]，记录每个单词到起点和终点的最短距离（如果尚未访问，则为无穷大）。
    • 维护一个父节点关系字典：parents[word] = []，列表存储所有能一步到达 word 的单词（在从起点开始的BFS中构建）。
    • 在每一轮中，选择当前层节点数较少的方向进行扩展（优化策略）。
    • 扩展节点时，生成当前单词所有可能的一次字母变换（例如，将每个位置依次替换为26个小写字母），检查新单词是否在 wordList 中。
    • 关键：当一个单词在从起点开始的BFS中被访问时，如果它是第一次被访问，或者当前路径的长度等于之前记录的最短距离，则将前驱单词加入 parents[新单词] 列表。
    • 当两个方向的搜索相遇（即某个单词同时被两个方向访问过），且满足 distanceFromBegin[word] + distanceFromEnd[word] == 最短路径长度 时，就找到了所有可能的最短路径的中间节点。

  3. 通过DFS回溯重建所有最短路径

    • 从 endWord 开始，使用深度优先搜索（DFS）沿着 parents 字典回溯到 beginWord。
    • 每次回溯时，将当前单词加入路径，然后递归地对其每一个父节点进行回溯。
    • 当回溯到 beginWord 时，将当前路径反转（因为是从终点回溯到起点），并添加到结果列表中。
    • 注意避免循环（由于我们只沿着最短路径回溯，且 parents 关系是在BFS中按层级构建的，所以天然无环）。

  4. 复杂度分析

    • 时间复杂度：O(N * L * 26)，其中 N 是 wordList 长度，L 是单词长度。最坏情况下需要探索所有单词的每个位置的可能变换。
    • 空间复杂度：O(N * L) 用于存储父节点关系和路径。

第五步：举例说明
假设：
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]。

  1. 双向BFS过程：
    • 起点BFS：hit -> hot
    • 终点BFS：cog -> dog, log
    • 继续扩展，最终找到路径长度为 5（hit->hot->dot->dog->cog 和 hit->hot->lot->log->cog）。
  2. 构建 parents 关系：
    例如，dog 的父节点可以是 dot（从起点方向），cog 的父节点可以是 dog 和 log。
  3. 回溯重建路径：
    从 cog 回溯，通过 dog 和 log 分别得到两条路径，反转后即得到最终答案。

这样，我们就得到了所有最短转换序列。这个算法通过双向BFS优化了搜索速度，并通过记录父节点列表来高效地重建所有路径，避免了暴力搜索所有可能路径的高昂成本。

LeetCode 127. 单词接龙 II 题目描述： 给定两个单词 beginWord 和 endWord ，以及一个单词列表 wordList 。要求找出所有从 beginWord 到 endWord 的最短转换序列，转换需遵循以下规则： 每次转换只能改变一个字母。 转换过程中的每个中间单词都必须在 wordList 中（ beginWord 不需要在列表中，但 endWord 必须在列表中）。 返回所有最短转换序列。如果不存在这样的转换序列，返回空列表。每个序列都应包含 beginWord 和 endWord ，且序列之间顺序任意。 解题过程循序渐进讲解： 第一步：问题理解与建模 这个问题本质上是在一个图（Graph）中寻找所有最短路径。图的节点是每个单词（包括 beginWord``），如果两个单词之间仅相差一个字母，则它们之间有一条无向边。目标是从起点 beginWord 到终点 endWord ` 的所有最短路径（即转换序列）。 第二步：基础思路——为什么不能简单用BFS？ 普通的广度优先搜索（BFS）可以找到一条最短路径，但本题要求找出“所有”最短路径。如果我们在BFS过程中，一旦找到 endWord 就停止，那么只能得到一条路径。而且，简单地记录所有路径可能导致搜索空间爆炸（因为要探索所有可能路径）。因此，我们需要一种能够系统地找出所有最短路径，同时避免指数级复杂度的算法。 第三步：核心算法——双向BFS + 层次化建图 一个高效的解法是结合 双向BFS 和 层次化建图 （也叫“广度优先搜索树”或“距离图”）。 双向BFS ：同时从 beginWord 和 endWord 开始进行BFS，当两个搜索相遇时，就找到了最短路径长度。这可以减少搜索的节点数量。 层次化建图 ：在BFS过程中，我们不仅记录每个节点到起点的距离（或层级），还记录每个节点的“父节点列表”（即哪些节点可以一步到达当前节点）。这样，我们在找到所有最短路径后，可以通过回溯从 endWord 到 beginWord 来重建所有路径。 第四步：具体步骤详解 预处理与检查 将 wordList 转换为集合（Set），便于 O(1) 时间查找。 检查 endWord 是否在集合中，如果不在，直接返回空列表。 双向BFS构建距离和父节点关系图 使用两个队列分别从起点（ beginWord ）和终点（ endWord ）开始BFS。 维护两个距离字典： distanceFromBegin[word] 和 distanceFromEnd[word] ，记录每个单词到起点和终点的最短距离（如果尚未访问，则为无穷大）。 维护一个父节点关系字典： parents[word] = [] ，列表存储所有能一步到达 word 的单词（在从起点开始的BFS中构建）。 在每一轮中，选择当前层节点数较少的方向进行扩展（优化策略）。 扩展节点时，生成当前单词所有可能的一次字母变换（例如，将每个位置依次替换为26个小写字母），检查新单词是否在 wordList 中。 关键 ：当一个单词在从起点开始的BFS中被访问时，如果它是第一次被访问，或者当前路径的长度等于之前记录的最短距离，则将前驱单词加入 parents[新单词] 列表。 当两个方向的搜索相遇（即某个单词同时被两个方向访问过），且满足 distanceFromBegin[word] + distanceFromEnd[word] == 最短路径长度 时，就找到了所有可能的最短路径的中间节点。 通过DFS回溯重建所有最短路径 从 endWord 开始，使用深度优先搜索（DFS）沿着 parents 字典回溯到 beginWord 。 每次回溯时，将当前单词加入路径，然后递归地对其每一个父节点进行回溯。 当回溯到 beginWord 时，将当前路径反转（因为是从终点回溯到起点），并添加到结果列表中。 注意避免循环（由于我们只沿着最短路径回溯，且 parents 关系是在BFS中按层级构建的，所以天然无环）。 复杂度分析 时间复杂度：O(N * L * 26)，其中 N 是 wordList 长度，L 是单词长度。最坏情况下需要探索所有单词的每个位置的可能变换。 空间复杂度：O(N * L) 用于存储父节点关系和路径。 第五步：举例说明 假设： beginWord = "hit" , endWord = "cog" , wordList = ["hot","dot","dog","lot","log","cog"] 。 双向BFS过程 ： 起点BFS： hit -> hot 终点BFS： cog -> dog , log 继续扩展，最终找到路径长度为 5（ hit -> hot -> dot -> dog -> cog 和 hit -> hot -> lot -> log -> cog ）。 构建 parents 关系 ： 例如， dog 的父节点可以是 dot （从起点方向）， cog 的父节点可以是 dog 和 log 。 回溯重建路径 ： 从 cog 回溯，通过 dog 和 log 分别得到两条路径，反转后即得到最终答案。 这样，我们就得到了所有最短转换序列。这个算法通过双向BFS优化了搜索速度，并通过记录父节点列表来高效地重建所有路径，避免了暴力搜索所有可能路径的高昂成本。