LeetCode 127. 单词接龙
字数 5713 2025-10-26 09:00:43

LeetCode 127. 单词接龙

题目描述

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

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

说明:

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

示例:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短的转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，所以它的长度是 5。

解题过程

这个问题可以被看作是在一个图中寻找两个节点之间的最短路径。我们可以这样理解：

  • 节点 (Node): 每一个单词就是一个节点。
  • 边 (Edge): 如果两个单词之间只有一个字母不同，那么它们之间就存在一条边（即可以进行一次转换）。

我们的目标是找到从起点 (beginWord) 到终点 (endWord) 的最短路径（边数最少）。对于最短路径问题，广度优先搜索 (BFS) 是一个非常自然且高效的选择，因为 BFS 会从起点开始，一层一层地向外探索，当第一次遇到终点时，所经过的层数就是最短路径的长度。

步骤 1: 基础 BFS 思路

  1. 预处理数据结构:

    • 将 wordList 转换为一个集合 (Set)，例如 wordSet。这样我们可以在 O(1) 时间内判断一个单词是否在字典中。
    • 创建一个队列 (Queue) 来进行 BFS。队列中存储的是当前正在探索的单词。
    • 创建一个集合 (visited) 来记录已经访问过的单词，避免重复访问和死循环。
    • 创建一个变量 (level) 来记录当前的层数（即转换序列的长度）。起点 beginWord 本身算作第 1 层。

  2. 初始化:

    • 将 beginWord 加入队列，并标记为已访问 (visited 集合中加入 beginWord)。
    • 初始化 level = 1（因为序列至少包含起点）。

  3. BFS 遍历:

    • 当队列不为空时，开始循环：
      a. 记录当前队列的大小 size（当前层的节点数量）。
      b. 对于当前层的每一个节点（单词）：
      i. 将其从队列中取出。
      ii. 如果这个单词等于 endWord，说明我们已经找到了终点，返回当前的 level。
      iii. 如果还不是终点，则生成这个单词的所有“邻居”。邻居是指与当前单词只有一个字母不同的、存在于 wordSet 中、且未被访问过的单词。
      iv. 将这些邻居单词加入队列，并标记为已访问。
      c. 处理完当前层的所有节点后，将 level 加 1，表示进入下一层。

  4. 终止条件:

    • 如果 BFS 结束（队列为空）都没有遇到 endWord，说明不存在转换序列，返回 0。

步骤 2: 关键优化 - 如何高效地寻找“邻居”？

最直接的方法是：对于一个长度为 L 的单词，我们尝试改变它的每一个位置的字母（从 ‘a’ 到 ‘z’），生成 26 * L 个新单词，然后判断哪些新单词存在于 wordSet 中。

但是，如果单词列表很大，这种方法在每一层都可能产生大量无效的判断（26 * L）。我们可以进行一个关键的优化：双向 BFS。

双向 BFS 思路:

  • 同时从起点 (beginWord) 和终点 (endWord) 开始进行 BFS。
  • 我们使用两个队列和两个已访问集合。
  • 在每一轮中，我们选择节点数较少的那一端进行扩展（这可以最小化搜索空间）。
  • 如果在扩展某一端的节点时，发现这个节点已经被另一端访问过了，那么我们就找到了一条连接起点和终点的路径。

双向 BFS 可以显著减少搜索的节点数量，尤其是在搜索空间较大时。

步骤 3: 双向 BFS 的详细步骤

  1. 边界条件检查:

    • 如果 endWord 根本不在 wordList 中，直接返回 0。

  2. 初始化:

    • wordSet: 将 wordList 转换为集合。
    • queue1: 用于从起点开始 BFS 的队列。初始加入 beginWord。
    • queue2: 用于从终点开始 BFS 的队列。初始加入 endWord。
    • visited1: 记录从起点端已访问的单词。初始加入 beginWord。
    • visited2: 记录从终点端已访问的单词。初始加入 endWord。
    • level = 1（起点和终点各自算作第1层，当它们相遇时，层数相加）。

  3. 核心循环:

    • 当 queue1 和 queue2 都非空时，循环继续：
      a. 总是优先扩展节点数较少的那一端（交换策略）。这样可以平衡两端的搜索规模。如果 queue1 的大小大于 queue2，我们就交换 queue1 和 queue2，同时交换 visited1 和 visited2。这样可以保证我们总是在扩展较小的一侧。
      b. 记录当前要扩展的队列 (queue1) 的当前大小 size。
      c. 对于这个队列中的 size 个单词：
      i. 取出一个单词 currentWord。
      ii. 生成这个单词的所有可能邻居（通过改变一个字母）。
      iii. 对于每一个生成的邻居单词 neighbor：
      * 如果 neighbor 在 wordSet 中：
      * 检查 neighbor 是否已经在另一端的已访问集合 (visited2) 中？如果是，恭喜！level + 1 就是最短路径长度（因为当前层从本端扩展到 neighbor，而 neighbor 已经在另一端被访问过，路径连通）。
      * 如果 neighbor 还不在本端的已访问集合 (visited1) 中，则将其加入队列和本端的已访问集合。
      d. 处理完当前层的所有节点后，将 level 加 1。

  4. 返回结果:

    • 如果循环结束都没有找到连通路径，返回 0。

举例说明（使用示例）:

beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

  1. 检查: "cog" 在 wordList 中。
  2. 初始化:
    • queue1 = ["hit"], visited1 = {"hit"}
    • queue2 = ["cog"], visited2 = {"cog"}
    • level = 1
  3. 第 1 轮循环: queue1 大小 (1) <= queue2 大小 (1)，扩展 queue1 端。
    • 处理 "hit":
      • 邻居: 改变第1位: it -> ait, bit, cit, ... , hit (跳过自身) -> 无。
        改变第2位: h_t -> hat, hbt, hct, ... , hot (在wordSet中!), ... , hzt。
        改变第3位: hi         -> hia, hib, ... , hil (不在wordSet中) -> 无。
      • 找到邻居 "hot"。
      • 检查 "hot" 在 visited2 中吗？{"cog"} 中没有。
      • "hot" 不在 visited1 中，将其加入 queue1 和 visited1。
    • 当前层处理完。level++ -> level = 2。
    • 现在 queue1 = ["hot"], visited1 = {"hit", "hot"}
  4. 第 2 轮循环: queue1 大小 (1) <= queue2 大小 (1)，扩展 queue1 端。
    • 处理 "hot":
      • 邻居: 改变第1位: ot -> aot, bot, ... , dot, ... , lot, ... , zot。
        改变第2位: h_t -> hat, hbt, ... , hit (已访问，跳过), ... , hzt。
        改变第3位: ho         -> hoa, hob, ... , hog (不在wordSet中), ... , hot (跳过) -> 无。
      • 找到邻居 "dot", "lot"。
      • 检查 "dot", "lot" 在 visited2 中吗？{"cog"} 中没有。
      • 将它们加入 queue1 和 visited1。
    • 当前层处理完。level++ -> level = 3。
    • 现在 queue1 = ["dot", "lot"], visited1 = {"hit", "hot", "dot", "lot"}
  5. 第 3 轮循环: queue1 大小 (2) > queue2 大小 (1)，交换！现在 queue1 (原queue2) = ["cog"], queue2 (原queue1) = ["dot", "lot"]。visited1 = {"cog"}, visited2 = {"hit", "hot", "dot", "lot"}。扩展新的 queue1 端（即从终点端开始扩展）。
    • 处理 "cog":
      • 邻居: 改变第1位: og -> aog, bog, ... , dog, log, ... , zog。
        改变第2位: c_g -> cag, cbg, ... , cog (跳过) -> 无。
        改变第3位: co         -> coa, cob, ... , cod (不在wordSet中), ... , **cot" (不在wordSet中) -> 无。
      • 找到邻居 "dog", "log"。
      • 检查 "dog", "log" 在 visited2 中吗？{"hit", "hot", "dot", "lot"} 中有 "dot" 和 "lot"！
      • 发现了交集！例如，对于 "dog"，它在 visited2 中吗？不在。对于 "log"，它在 visited2 中吗？不在。等等，我们需要检查的是，新扩展出的节点是否在另一端的已访问集合里。我们扩展的是终点端 (queue1)，另一端是起点端 (visited2)。"dog" 和 "log" 目前还不在 visited2 里。所以暂时没有直接连通。我们将 "dog" 和 "log" 加入 queue1 和 visited1。
    • 当前层处理完。level++ -> level = 4。
    • 现在 queue1 = [] (已处理完 "cog")，新加入的 "dog", "log" 会在下一轮被处理？不，我们是在处理当前层的大小，新节点是下一层。所以现在 queue1 实际上是 ["dog", "log"]? 这里需要理解：我们处理的是旧的 queue1（大小为1，只有 "cog"），处理完后，queue1 中是新加入的 "dog" 和 "log"。所以 queue1 现在是 ["dog", "log"]。visited1 = {"cog", "dog", "log"}
  6. 第 4 轮循环: queue1 大小 (2) <= queue2 大小 (2)（queue2 是 ["dot", "lot"]），扩展 queue1 端（终点端）。
    • 处理 "dog":
      • 邻居: ... 会生成 "dot", "cog" 等。"cog" 已访问。"dot" 在 wordSet 中。
      • 检查 "dot" 是否在 visited2 中？ visited2 是 {"hit", "hot", "dot", "lot"}，包含 "dot"！
      • 找到连通路径！ 路径是 hit(1) -> hot(2) -> dot(3) [起点端] 和 cog(1) -> dog(2) [终点端]。相遇在 "dot" 和 "dog" 的连接上。总长度为 3 + 2 = 5？ 更准确地说，起点端到 "dot" 是 3 步，终点端到 "dog" 是 2 步，"dot" 和 "dog" 之间相差 1 步。所以总转换序列是 3 + 2 = 5？ 实际上，在 BFS 中，我们是从两端分别计数的。当我们在终点端扩展 "dog" 时，发现它的邻居 "dot" 已经被起点端访问过了。此时的 level 是 4（终点端当前是第4层？我们需要重新审视计数）。

让我们重新校准计数：

  • 起点端 BFS 层数：beginWord 是第 1 层。
    • 第1层: "hit"
    • 第2层: "hot"
    • 第3层: "dot", "lot"
  • 终点端 BFS 层数：endWord 是第 1 层。
    • 第1层: "cog"
    • 第2层: "dog", "log"

当我们在终点端处理第2层的节点 "dog" 时，发现它的邻居 "dot" 在起点端的第3层已被访问。此时，总路径长度是起点端层数 (3) + 终点端层数 (2) = 5。在代码实现中，我们通常用一个 level 变量，在两端相遇时返回 level 的值，这个值就是总长度。

通过这个例子，你可以看到双向 BFS 如何高效地找到了最短路径。

LeetCode 127. 单词接龙 题目描述 给定两个单词（ beginWord 和 endWord ）和一个字典（ wordList ），你需要找到从 beginWord 到 endWord 的最短转换序列的长度。转换需要遵循以下规则： 每次转换只能改变一个字母。 转换过程中的每个中间单词都必须是字典 wordList 中的单词。 说明: 如果不存在这样的转换序列，返回 0。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。 示例: 输入: beginWord = "hit", endWord = "cog", wordList = [ "hot","dot","dog","lot","log","cog" ] 输出: 5 解释: 一个最短的转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，所以它的长度是 5。 解题过程 这个问题可以被看作是在一个图中寻找两个节点之间的最短路径。我们可以这样理解： 节点 (Node): 每一个单词就是一个节点。 边 (Edge): 如果两个单词之间只有一个字母不同，那么它们之间就存在一条边（即可以进行一次转换）。 我们的目标是找到从起点 ( beginWord ) 到终点 ( endWord ) 的最短路径（边数最少）。对于最短路径问题， 广度优先搜索 (BFS) 是一个非常自然且高效的选择，因为 BFS 会从起点开始，一层一层地向外探索，当第一次遇到终点时，所经过的层数就是最短路径的长度。 步骤 1: 基础 BFS 思路 预处理数据结构: 将 wordList 转换为一个集合 ( Set )，例如 wordSet 。这样我们可以在 O(1) 时间内判断一个单词是否在字典中。 创建一个队列 ( Queue ) 来进行 BFS。队列中存储的是当前正在探索的单词。 创建一个集合 ( visited ) 来记录已经访问过的单词，避免重复访问和死循环。 创建一个变量 ( level ) 来记录当前的层数（即转换序列的长度）。起点 beginWord 本身算作第 1 层。 初始化: 将 beginWord 加入队列，并标记为已访问 ( visited 集合中加入 beginWord )。 初始化 level = 1 （因为序列至少包含起点）。 BFS 遍历: 当队列不为空时，开始循环： a. 记录当前队列的大小 size （当前层的节点数量）。 b. 对于当前层的每一个节点（单词）： i. 将其从队列中取出。 ii. 如果这个单词等于 endWord ，说明我们已经找到了终点，返回当前的 level 。 iii. 如果还不是终点，则生成这个单词的所有“邻居”。邻居是指与当前单词只有一个字母不同的、存在于 wordSet 中、且未被访问过的单词。 iv. 将这些邻居单词加入队列，并标记为已访问。 c. 处理完当前层的所有节点后，将 level 加 1，表示进入下一层。 终止条件: 如果 BFS 结束（队列为空）都没有遇到 endWord ，说明不存在转换序列，返回 0。 步骤 2: 关键优化 - 如何高效地寻找“邻居”？ 最直接的方法是：对于一个长度为 L 的单词，我们尝试改变它的每一个位置的字母（从 ‘a’ 到 ‘z’），生成 26 * L 个新单词，然后判断哪些新单词存在于 wordSet 中。 但是，如果单词列表很大，这种方法在每一层都可能产生大量无效的判断（26 * L）。我们可以进行一个关键的优化： 双向 BFS 。 双向 BFS 思路: 同时从起点 ( beginWord ) 和终点 ( endWord ) 开始进行 BFS。 我们使用两个队列和两个已访问集合。 在每一轮中，我们选择节点数较少的那一端进行扩展（这可以最小化搜索空间）。 如果在扩展某一端的节点时，发现这个节点已经被另一端访问过了，那么我们就找到了一条连接起点和终点的路径。 双向 BFS 可以显著减少搜索的节点数量，尤其是在搜索空间较大时。 步骤 3: 双向 BFS 的详细步骤 边界条件检查: 如果 endWord 根本不在 wordList 中，直接返回 0。 初始化: wordSet : 将 wordList 转换为集合。 queue1 : 用于从起点开始 BFS 的队列。初始加入 beginWord 。 queue2 : 用于从终点开始 BFS 的队列。初始加入 endWord 。 visited1 : 记录从起点端已访问的单词。初始加入 beginWord 。 visited2 : 记录从终点端已访问的单词。初始加入 endWord 。 level = 1 （起点和终点各自算作第1层，当它们相遇时，层数相加）。 核心循环: 当 queue1 和 queue2 都非空时，循环继续： a. 总是优先扩展节点数较少的那一端 （交换策略）。这样可以平衡两端的搜索规模。如果 queue1 的大小大于 queue2 ，我们就交换 queue1 和 queue2 ，同时交换 visited1 和 visited2 。这样可以保证我们总是在扩展较小的一侧。 b. 记录当前要扩展的队列 ( queue1 ) 的当前大小 size 。 c. 对于这个队列中的 size 个单词： i. 取出一个单词 currentWord 。 ii. 生成这个单词的所有可能邻居（通过改变一个字母）。 iii. 对于每一个生成的邻居单词 neighbor ： * 如果 neighbor 在 wordSet 中： * 检查 neighbor 是否已经在 另一端 的已访问集合 ( visited2 ) 中？如果是，恭喜！ level + 1 就是最短路径长度（因为当前层从本端扩展到 neighbor ，而 neighbor 已经在另一端被访问过，路径连通）。 * 如果 neighbor 还 不在本端 的已访问集合 ( visited1 ) 中，则将其加入队列和本端的已访问集合。 d. 处理完当前层的所有节点后，将 level 加 1。 返回结果: 如果循环结束都没有找到连通路径，返回 0。 举例说明（使用示例）: beginWord = "hit", endWord = "cog", wordList = [ "hot","dot","dog","lot","log","cog" ] 检查: "cog" 在 wordList 中。 初始化: queue1 = [ "hit"], visited1 = {"hit"} queue2 = [ "cog"], visited2 = {"cog"} level = 1 第 1 轮循环: queue1 大小 (1) <= queue2 大小 (1)，扩展 queue1 端。 处理 "hit": 邻居: 改变第1位: it -> ait, bit, cit, ... , hit (跳过自身) -> 无。 改变第2位: h_ t -> hat, hbt, hct, ... , hot (在wordSet中 !), ... , hzt。 改变第3位: hi -> hia, hib, ... , hil (不在wordSet中) -> 无。 找到邻居 "hot"。 检查 "hot" 在 visited2 中吗？{"cog"} 中没有。 "hot" 不在 visited1 中，将其加入 queue1 和 visited1 。 当前层处理完。 level++ -> level = 2 。 现在 queue1 = [ "hot"], visited1 = {"hit", "hot"} 第 2 轮循环: queue1 大小 (1) <= queue2 大小 (1)，扩展 queue1 端。 处理 "hot": 邻居: 改变第1位: ot -> aot, bot, ... , dot , ... , lot , ... , zot。 改变第2位: h_ t -> hat, hbt, ... , hit (已访问，跳过), ... , hzt。 改变第3位: ho -> hoa, hob, ... , hog (不在wordSet中), ... , hot (跳过) -> 无。 找到邻居 "dot", "lot"。 检查 "dot", "lot" 在 visited2 中吗？{"cog"} 中没有。 将它们加入 queue1 和 visited1 。 当前层处理完。 level++ -> level = 3 。 现在 queue1 = [ "dot", "lot"], visited1 = {"hit", "hot", "dot", "lot"} 第 3 轮循环: queue1 大小 (2) > queue2 大小 (1)， 交换 ！现在 queue1 (原queue2) = [ "cog"], queue2 (原queue1) = [ "dot", "lot"]。 visited1 = {"cog"}, visited2 = {"hit", "hot", "dot", "lot"}。扩展新的 queue1 端（即从终点端开始扩展）。 处理 "cog": 邻居: 改变第1位: og -> aog, bog, ... , dog , log , ... , zog。 改变第2位: c_ g -> cag, cbg, ... , cog (跳过) -> 无。 改变第3位: co -> coa, cob, ... , cod (不在wordSet中), ... , ** cot" (不在wordSet中) -> 无。 找到邻居 "dog", "log"。 检查 "dog", "log" 在 visited2 中吗？{"hit", "hot", "dot", "lot"} 中 有 "dot" 和 "lot" ！ 发现了交集！例如，对于 "dog"，它在 visited2 中吗？不在。对于 "log"，它在 visited2 中吗？不在。等等，我们需要检查的是，新扩展出的节点是否在 另一端 的已访问集合里。我们扩展的是终点端 ( queue1 )，另一端是起点端 ( visited2 )。"dog" 和 "log" 目前还不在 visited2 里。所以暂时没有直接连通。我们将 "dog" 和 "log" 加入 queue1 和 visited1 。 当前层处理完。 level++ -> level = 4 。 现在 queue1 = [] (已处理完 "cog")，新加入的 "dog", "log" 会在下一轮被处理？不，我们是在处理当前层的大小，新节点是下一层。所以现在 queue1 实际上是 [ "dog", "log"]? 这里需要理解：我们处理的是旧的 queue1 （大小为1，只有 "cog"），处理完后， queue1 中是新加入的 "dog" 和 "log"。所以 queue1 现在是 [ "dog", "log"]。 visited1 = {"cog", "dog", "log"} 第 4 轮循环: queue1 大小 (2) <= queue2 大小 (2)（ queue2 是 [ "dot", "lot"]），扩展 queue1 端（终点端）。 处理 "dog": 邻居: ... 会生成 "dot", "cog" 等。"cog" 已访问。"dot" 在 wordSet 中。 检查 "dot" 是否在 visited2 中？ visited2 是 {"hit", "hot", "dot", "lot"}， 包含 "dot" ！ 找到连通路径！ 路径是 hit(1) -> hot(2) -> dot(3) [ 起点端] 和 cog(1) -> dog(2) [ 终点端]。相遇在 "dot" 和 "dog" 的连接上。总长度为 3 + 2 = 5？ 更准确地说，起点端到 "dot" 是 3 步，终点端到 "dog" 是 2 步，"dot" 和 "dog" 之间相差 1 步。所以总转换序列是 3 + 2 = 5？ 实际上，在 BFS 中，我们是从两端分别计数的。当我们在终点端扩展 "dog" 时，发现它的邻居 "dot" 已经被起点端访问过了。此时的 level 是 4（终点端当前是第4层？我们需要重新审视计数）。 让我们重新校准计数： 起点端 BFS 层数： beginWord 是第 1 层。 第1层: "hit" 第2层: "hot" 第3层: "dot", "lot" 终点端 BFS 层数： endWord 是第 1 层。 第1层: "cog" 第2层: "dog", "log" 当我们在终点端处理第2层的节点 "dog" 时，发现它的邻居 "dot" 在起点端的第3层已被访问。此时，总路径长度是起点端层数 (3) + 终点端层数 (2) = 5。在代码实现中，我们通常用一个 level 变量，在两端相遇时返回 level 的值，这个值就是总长度。 通过这个例子，你可以看到双向 BFS 如何高效地找到了最短路径。