单词接龙
字数 3909 2025-12-24 08:03:45

好的，我们来看一个尚未讲过的、结合了哈希算法与双向搜索思想的经典题目。

单词接龙

题目描述

给你两个单词 beginWord 和 endWord，以及一个单词列表 wordList。你需要找到从 beginWord 到 endWord 的 最短转换序列 的长度。转换必须遵循以下规则：

  1. 每次转换只能改变一个字母。
  2. 转换过程中的每个单词（包括 beginWord）都必须在 wordList 中。注意，beginWord 不一定在 wordList 里，而 endWord 必须在 wordList 中。

如果不存在这样的转换序列，则返回 0。

示例：
输入：
beginWord = “hit”
endWord = “cog”
wordList = [“hot”, “dot”, “dog”, “lot”, “log”, “cog”]
输出：5
解释：一个最短的转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”，其长度为 5（单词数）。

解题过程循序渐进讲解

第一步：理解问题与抽象建模

首先，我们把问题抽象成一个 图论 问题。

  • 节点： 每个单词就是一个节点。
  • 边： 如果两个单词之间 只有一个字母不同，那么它们之间就有一条无向边（因为转换是可逆的）。
  • 目标： 在图中找到从起点节点 (beginWord) 到终点节点 (endWord) 的 最短路径长度。由于每条边的权重都是1（一次转换），所以我们可以用 广度优先搜索 (BFS) 来寻找最短路径。

BFS 好比一滴墨水从起点滴入水中，一层一层均匀地向外扩散，当它首次碰到终点时，扩散的层数就是最短距离。

第二步：基础BFS框架

我们先构建一个基础的 BFS 框架。

  1. 初始化：

    • 将 beginWord 放入队列作为第一层。
    • 创建一个 HashSet visited，用于记录已经访问过的单词，避免走回头路。将 beginWord 加入 visited。
    • 创建一个 HashSet wordSet，将 wordList 中的所有单词放入其中。这样我们可以在 O(1) 时间内判断一个单词是否在合法单词列表中，这是哈希表的核心作用之一。
    • 路径长度 level 初始化为 1（因为起点本身算一个单词）。

  2. BFS循环：

    • 当队列不为空时，进行循环。
    • 处理当前层的所有节点（记录当前队列大小 size，然后循环 size 次）。
      • 弹出队首单词 currentWord。
      • 如果 currentWord 等于 endWord，则返回当前 level。
      • 否则，生成 currentWord 的所有可能的下一个单词（邻居）。
      • 对于每个邻居 nextWord，如果它在 wordSet 中 并且 没有被访问过 (!visited.contains(nextWord))，则将其加入队列和 visited 集合。
    • 处理完当前层所有节点后，level 加 1，进入下一层。

  3. 如果BFS结束仍未找到终点，返回 0。

第三步：关键优化——如何高效寻找“邻居”

基础BFS的瓶颈在于寻找邻居。对于一个长度为 L 的单词，最直接的方法是遍历整个 wordList (大小为 N)，逐个比较，时间复杂度为 O(N * L)，在最坏情况下（每次都要遍历整个列表）会变成 O(N² * L)，效率低下。

核心优化策略（使用哈希思想）：
我们采用 “模式匹配” 的思路。对于单词 "hit"，它的邻居模式有：

  • “*it” (对应如 “bit”, “fit” 等)
  • “h*t” (对应如 “hot”, “hat” 等)
  • “hi*” (对应如 “hip”, “his” 等)

我们可以 预计算一个“模式 -> 单词列表”的哈希表 (patternMap)。

预计算过程：

  • 遍历 wordList 中的每个单词 word。
  • 对于 word 的每个位置 i (从 0 到 L-1)，生成一个模式字符串：word.substring(0, i) + “*” + word.substring(i+1)。
  • 将这个模式作为键，将 word 添加到该键对应的值（一个列表）中。
    例如，对于 wordList = [“hot”, “dot”, “dog”]：
    • “hot” 生成模式：“*ot”, “h*t”, “ho*”。
    • “dot” 生成模式：“*ot”, “d*t”, “do*”。
    • 那么 patternMap[“*ot”] 就会包含 [“hot”, “dot”]。

在BFS中寻找邻居：
当我们需要找到 currentWord (例如 “hit”) 的所有邻居时：

  1. 同样为 currentWord 生成它的所有 L 个模式。
  2. 对于每个模式，去 patternMap 中查找，该模式下的所有单词 都是 currentWord 的潜在邻居。
  3. 再从这些潜在邻居中，筛选出未被访问过的。

这样，寻找邻居的时间复杂度就降低到了 O(L²)（生成L个模式，每个模式下的单词平均长度是L），而与总单词数 N 无关，效率得到质的提升。

第四步：进一步优化——双向BFS

基础BFS是从起点单向扩散。想象一下，如果从起点和终点 同时开始扩散，当两个方向的搜索相遇时，总搜索范围会大大减小，尤其是在解位于中间位置时。

双向BFS算法步骤：

  1. 初始化两个队列 queueBegin 和 queueEnd，两个已访问集合 visitedBegin 和 visitedEnd。
  2. 将 beginWord 加入 queueBegin 和 visitedBegin（值记录为从起点开始的层次）。
  3. 将 endWord 加入 queueEnd 和 visitedEnd（值记录为从终点开始的层次，或一个特殊标记）。
  4. 每次选择 当前待探索节点数较少 的那个方向进行一步BFS（这有助于平衡搜索）。
  5. 在每一步中，检查当前节点 currentWord 是否出现在 另一个方向 的已访问集合中。
    • 如果出现，说明两股搜索“相遇”。相遇路径的长度 = levelBegin + levelEnd（或根据存储的层级信息计算）。
  6. 如果某个队列为空，说明该方向已无法前进，而两个方向仍未相遇，则转换失败。

双向BFS结合模式匹配的哈希表，是本问题最高效的解决方案之一。

第五步：完整算法步骤梳理

  1. 边界检查：如果 endWord 不在 wordList 转换的 wordSet 中，直接返回 0。
  2. 构建模式哈希表 (patternMap)：遍历 wordList，为每个单词的每个位置生成通配符模式，并建立映射。
  3. 初始化双向BFS：
    • queueBegin = [beginWord], visitedBegin = {beginWord: 1}
    • queueEnd = [endWord], visitedEnd = {endWord: 1}
    • level = 1 (这里我们两边都从第1层开始计数)
  4. 双向BFS主循环 (当两个队列都不空时)：
    a. 选择搜索方向：总是从节点数少的队列开始扩展，假设这次我们从 queueBegin 扩展。
    b. 处理当前层：记下 queueBegin 当前大小 size，循环 size 次。
    - 弹出队首 word。
    - 为 word 生成所有 L 个模式。
    - 对每个模式，从 patternMap 中获取邻居列表。
    - 遍历每个邻居 nextWord：
    i. 如果 nextWord 在 visitedEnd 中，则 相遇！返回 visitedBegin[word] + visitedEnd[nextWord]。
    ii. 如果 nextWord 不在 visitedBegin 中：
    - 将其加入 queueBegin。
    - 在 visitedBegin 中记录 visitedBegin[nextWord] = visitedBegin[word] + 1。
    c. 交换 queueBegin / visitedBegin 与 queueEnd / visitedEnd 的角色（确保下一轮扩展另一边），level 递增的逻辑隐含在 visited 记录的层级中。
  5. 如果循环结束仍未返回，说明两股搜索无法相遇，返回 0。

总结：
单词接龙 问题巧妙地结合了：

  1. 哈希集合 (wordSet)： 用于 O(1) 的成员资格检查。
  2. 哈希映射 (patternMap)： 核心优化，将“寻找邻居”的复杂度从 O(N) 降至 O(L)，通过预计算“模式”到“单词”的映射。
  3. 广度优先搜索 (BFS)： 用于寻找无权图的最短路径。
  4. 双向BFS： 高级优化策略，从起点和终点同时搜索，大幅减少搜索空间，尤其在路径较长时效果显著。

这个题目完整地展示了如何利用哈希数据结构来优化图搜索算法中的关键步骤，是理解算法与数据结构结合的优秀范例。

好的，我们来看一个尚未讲过的、结合了哈希算法与双向搜索思想的经典题目。 单词接龙 题目描述 给你两个单词 beginWord 和 endWord ，以及一个单词列表 wordList 。你需要找到从 beginWord 到 endWord 的 最短转换序列 的长度。转换必须遵循以下规则： 每次转换只能改变一个字母。 转换过程中的每个单词（包括 beginWord ）都必须在 wordList 中。注意， beginWord 不一定在 wordList 里，而 endWord 必须在 wordList 中。 如果不存在这样的转换序列，则返回 0。 示例： 输入： beginWord = “hit” endWord = “cog” wordList = [“hot”, “dot”, “dog”, “lot”, “log”, “cog”] 输出：5 解释：一个最短的转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”，其长度为 5（单词数）。 解题过程循序渐进讲解 第一步：理解问题与抽象建模 首先，我们把问题抽象成一个 图论 问题。 节点 ： 每个单词就是一个节点。 边 ： 如果两个单词之间 只有一个字母不同 ，那么它们之间就有一条无向边（因为转换是可逆的）。 目标 ： 在图中找到从起点节点 ( beginWord ) 到终点节点 ( endWord ) 的 最短路径长度 。由于每条边的权重都是1（一次转换），所以我们可以用 广度优先搜索 (BFS) 来寻找最短路径。 BFS 好比一滴墨水从起点滴入水中，一层一层均匀地向外扩散，当它首次碰到终点时，扩散的层数就是最短距离。 第二步：基础BFS框架 我们先构建一个基础的 BFS 框架。 初始化 ： 将 beginWord 放入队列作为第一层。 创建一个 HashSet visited ，用于记录已经访问过的单词，避免走回头路。将 beginWord 加入 visited 。 创建一个 HashSet wordSet ，将 wordList 中的所有单词放入其中。这样我们可以在 O(1) 时间内判断一个单词是否在合法单词列表中，这是哈希表的核心作用之一。 路径长度 level 初始化为 1（因为起点本身算一个单词）。 BFS循环 ： 当队列不为空时，进行循环。 处理当前层的所有节点（记录当前队列大小 size ，然后循环 size 次）。 弹出队首单词 currentWord 。 如果 currentWord 等于 endWord ，则返回当前 level 。 否则， 生成 currentWord 的所有可能的下一个单词（邻居） 。 对于每个邻居 nextWord ，如果它在 wordSet 中 并且 没有被访问过 ( !visited.contains(nextWord) )，则将其加入队列和 visited 集合。 处理完当前层所有节点后， level 加 1，进入下一层。 如果BFS结束仍未找到终点 ，返回 0。 第三步：关键优化——如何高效寻找“邻居” 基础BFS的瓶颈在于寻找邻居。对于一个长度为 L 的单词，最直接的方法是遍历整个 wordList (大小为 N)，逐个比较，时间复杂度为 O(N * L)，在最坏情况下（每次都要遍历整个列表）会变成 O(N² * L)，效率低下。 核心优化策略（使用哈希思想） ： 我们采用 “模式匹配” 的思路。对于单词 "hit" ，它的邻居模式有： “*it” (对应如 “bit”, “fit” 等) “h*t” (对应如 “hot”, “hat” 等) “hi*” (对应如 “hip”, “his” 等) 我们可以 预计算一个“模式 -> 单词列表”的哈希表 ( patternMap ) 。 预计算过程 ： 遍历 wordList 中的每个单词 word 。 对于 word 的每个位置 i (从 0 到 L-1)，生成一个模式字符串： word.substring(0, i) + “*” + word.substring(i+1) 。 将这个模式作为键，将 word 添加到该键对应的值（一个列表）中。 例如，对于 wordList = [“hot”, “dot”, “dog”] ： “hot” 生成模式： “*ot” , “h*t” , “ho*” 。 “dot” 生成模式： “*ot” , “d*t” , “do*” 。 那么 patternMap[“*ot”] 就会包含 [“hot”, “dot”] 。 在BFS中寻找邻居 ： 当我们需要找到 currentWord (例如 “hit” ) 的所有邻居时： 同样为 currentWord 生成它的所有 L 个模式。 对于每个模式，去 patternMap 中查找，该模式下的所有单词 都是 currentWord 的潜在邻居 。 再从这些潜在邻居中，筛选出未被访问过的。 这样，寻找邻居的时间复杂度就降低到了 O(L²) （生成L个模式，每个模式下的单词平均长度是L），而与总单词数 N 无关，效率得到质的提升。 第四步：进一步优化——双向BFS 基础BFS是从起点单向扩散。想象一下，如果从起点和终点 同时开始扩散 ，当两个方向的搜索相遇时，总搜索范围会大大减小，尤其是在解位于中间位置时。 双向BFS算法步骤 ： 初始化两个队列 queueBegin 和 queueEnd ，两个已访问集合 visitedBegin 和 visitedEnd 。 将 beginWord 加入 queueBegin 和 visitedBegin （值记录为从起点开始的层次）。 将 endWord 加入 queueEnd 和 visitedEnd （值记录为从终点开始的层次，或一个特殊标记）。 每次选择 当前待探索节点数较少 的那个方向进行一步BFS（这有助于平衡搜索）。 在每一步中，检查当前节点 currentWord 是否出现在 另一个方向 的已访问集合中。 如果出现，说明两股搜索“相遇”。相遇路径的长度 = levelBegin + levelEnd （或根据存储的层级信息计算）。 如果某个队列为空，说明该方向已无法前进，而两个方向仍未相遇，则转换失败。 双向BFS结合模式匹配的哈希表，是本问题最高效的解决方案之一。 第五步：完整算法步骤梳理 边界检查 ：如果 endWord 不在 wordList 转换的 wordSet 中，直接返回 0。 构建模式哈希表 ( patternMap ) ：遍历 wordList ，为每个单词的每个位置生成通配符模式，并建立映射。 初始化双向BFS ： queueBegin = [beginWord] , visitedBegin = {beginWord: 1} queueEnd = [endWord] , visitedEnd = {endWord: 1} level = 1 (这里我们两边都从第1层开始计数) 双向BFS主循环 (当两个队列都不空时)： a. 选择搜索方向 ：总是从节点数少的队列开始扩展，假设这次我们从 queueBegin 扩展。 b. 处理当前层 ：记下 queueBegin 当前大小 size ，循环 size 次。 - 弹出队首 word 。 - 为 word 生成所有 L 个模式。 - 对每个模式，从 patternMap 中获取邻居列表。 - 遍历每个邻居 nextWord ： i. 如果 nextWord 在 visitedEnd 中，则 相遇 ！返回 visitedBegin[word] + visitedEnd[nextWord] 。 ii. 如果 nextWord 不在 visitedBegin 中： - 将其加入 queueBegin 。 - 在 visitedBegin 中记录 visitedBegin[nextWord] = visitedBegin[word] + 1 。 c. 交换 queueBegin / visitedBegin 与 queueEnd / visitedEnd 的角色（确保下一轮扩展另一边）， level 递增的逻辑隐含在 visited 记录的层级中。 如果循环结束仍未返回，说明两股搜索无法相遇，返回 0。 总结 ： 单词接龙 问题巧妙地结合了： 哈希集合 ( wordSet ) ： 用于 O(1) 的成员资格检查。 哈希映射 ( patternMap ) ： 核心优化，将“寻找邻居”的复杂度从 O(N) 降至 O(L)，通过预计算“模式”到“单词”的映射。 广度优先搜索 (BFS) ： 用于寻找无权图的最短路径。 双向BFS ： 高级优化策略，从起点和终点同时搜索，大幅减少搜索空间，尤其在路径较长时效果显著。 这个题目完整地展示了如何利用哈希数据结构来优化图搜索算法中的关键步骤，是理解算法与数据结构结合的优秀范例。