LeetCode 127. 单词接龙

字数 1618 2025-10-30 17:43:25

LeetCode 127. 单词接龙

题目描述：
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

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

说明:

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

解题过程：

这个问题可以建模为一个图论中的最短路径问题。每个单词是图中的一个节点，如果两个单词之间只有一个字母不同，那么它们之间有一条无向边。我们的目标是找到从 beginWord 节点到 endWord 节点的最短路径（边数最少）。

预处理与图构建
直接比较每对单词来判断是否相连，时间复杂度会很高（O(N^2 * L)，其中 N 是单词数量，L 是单词长度）。一个更高效的方法是使用“通配符”预处理。
- 思路：对于单词 hit，我们生成它所有可能的“通用状态”：*it，h*t，hi*。所有能映射到同一个通用状态的单词都是相连的。
- 方法：我们创建一个字典（邻接表），键是通用状态，值是属于这个状态的所有单词的列表。这样，对于任何一个单词，我们只需要生成它的 L 种通用状态，就能快速找到所有与它相邻的单词。
广度优先搜索（BFS）
由于边的权重都是1（每次转换一步），BFS是求解无权图单源最短路径的理想算法。BFS会一层一层地遍历节点，第一次遇到目标节点时，经过的层数就是最短路径长度。
- 初始化：
  - 创建一个队列，用于BFS遍历。将起始单词 beginWord 加入队列。
  - 创建一个集合（或字典），用于记录已经访问过的单词，以避免重复访问和死循环。将 beginWord 加入已访问集合。
  - 将路径长度（层数）初始化为 1，因为 beginWord 本身算作序列的第一个单词。
- BFS遍历：
  - 当队列不为空时，开始处理当前层的所有节点。
  - 获取当前队列的大小（即当前层的节点数）。
  - 对于当前层的每一个单词：
    - 弹出这个单词。
    - 如果这个单词就是 endWord，我们找到了目标，返回当前的路径长度。
    - 否则，生成这个单词的所有 L 个通用状态。
    - 对于每个通用状态，找到字典中所有与该状态相邻且未被访问过的单词。
    - 将这些新单词标记为已访问，并加入队列，它们属于下一层。
  - 处理完当前层的所有节点后，将路径长度加 1，意味着我们即将进入下一层。
双向BFS优化
当搜索空间很大时，传统的BFS（从起点单向搜索）可能会探索过多的节点。双向BFS是一种优化，它同时从起点和终点开始进行BFS。
- 思路：用两个集合分别代替两个队列，表示从起点开始的“前沿”和从终点开始的“前沿”。每次选择较小的那个前沿进行扩展，检查扩展出的新节点是否出现在另一个前沿中。如果出现，则说明两条路径相遇，找到了最短路径。
- 优点：从起点和终点同时搜索，可以显著减少需要探索的节点数量，从而加快搜索速度。

总结步骤：

检查 endWord 是否在 wordList 中，如果不在，直接返回 0。
对 wordList 进行预处理，构建通用状态到单词的映射字典。
使用队列和已访问集合进行BFS（或使用两个集合进行双向BFS）。
在BFS的每一层，将当前单词转换为所有通用状态，并找到相邻的未访问单词。
如果遇到 endWord，返回当前层数。
如果BFS结束仍未遇到 endWord，返回 0。

这个算法通过将单词转换问题抽象为图遍历，并利用BFS的特性，高效地找到了最短转换序列。预处理步骤是关键，它将寻找邻接关系的时间复杂度从 O(N^2 * L) 降低到了 O(N * L^2)。

LeetCode 127. 单词接龙题目描述：给定两个单词（beginWord 和 endWord）和一个字典 wordList，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：每次转换只能改变一个字母。转换过程中的中间单词必须是字典 wordList 中的单词。说明: 如果不存在这样的转换序列，返回 0。所有单词具有相同的长度。所有单词只由小写字母组成。字典中不存在重复的单词。你可以假设 beginWord 和 endWord 是非空的，且二者不相同。解题过程：这个问题可以建模为一个图论中的最短路径问题。每个单词是图中的一个节点，如果两个单词之间只有一个字母不同，那么它们之间有一条无向边。我们的目标是找到从 beginWord 节点到 endWord 节点的最短路径（边数最少）。预处理与图构建直接比较每对单词来判断是否相连，时间复杂度会很高（O(N^2 * L)，其中 N 是单词数量，L 是单词长度）。一个更高效的方法是使用“通配符”预处理。思路：对于单词 hit ，我们生成它所有可能的“通用状态”： *it ， h*t ， hi* 。所有能映射到同一个通用状态的单词都是相连的。方法：我们创建一个字典（邻接表），键是通用状态，值是属于这个状态的所有单词的列表。这样，对于任何一个单词，我们只需要生成它的 L 种通用状态，就能快速找到所有与它相邻的单词。广度优先搜索（BFS）由于边的权重都是1（每次转换一步），BFS是求解无权图单源最短路径的理想算法。BFS会一层一层地遍历节点，第一次遇到目标节点时，经过的层数就是最短路径长度。初始化：创建一个队列，用于BFS遍历。将起始单词 beginWord 加入队列。创建一个集合（或字典），用于记录已经访问过的单词，以避免重复访问和死循环。将 beginWord 加入已访问集合。将路径长度（层数）初始化为 1，因为 beginWord 本身算作序列的第一个单词。 BFS遍历：当队列不为空时，开始处理当前层的所有节点。获取当前队列的大小（即当前层的节点数）。对于当前层的每一个单词：弹出这个单词。如果这个单词就是 endWord ，我们找到了目标，返回当前的路径长度。否则，生成这个单词的所有 L 个通用状态。对于每个通用状态，找到字典中所有与该状态相邻且未被访问过的单词。将这些新单词标记为已访问，并加入队列，它们属于下一层。处理完当前层的所有节点后，将路径长度加 1，意味着我们即将进入下一层。双向BFS优化当搜索空间很大时，传统的BFS（从起点单向搜索）可能会探索过多的节点。双向BFS是一种优化，它同时从起点和终点开始进行BFS。思路：用两个集合分别代替两个队列，表示从起点开始的“前沿”和从终点开始的“前沿”。每次选择较小的那个前沿进行扩展，检查扩展出的新节点是否出现在另一个前沿中。如果出现，则说明两条路径相遇，找到了最短路径。优点：从起点和终点同时搜索，可以显著减少需要探索的节点数量，从而加快搜索速度。总结步骤：检查 endWord 是否在 wordList 中，如果不在，直接返回 0。对 wordList 进行预处理，构建通用状态到单词的映射字典。使用队列和已访问集合进行BFS（或使用两个集合进行双向BFS）。在BFS的每一层，将当前单词转换为所有通用状态，并找到相邻的未访问单词。如果遇到 endWord ，返回当前层数。如果BFS结束仍未遇到 endWord ，返回 0。这个算法通过将单词转换问题抽象为图遍历，并利用BFS的特性，高效地找到了最短转换序列。预处理步骤是关键，它将寻找邻接关系的时间复杂度从 O(N^2 * L) 降低到了 O(N * L^2)。