单词接龙
字数 2909 2025-12-24 18:34:46

单词接龙

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

  1. 每次转换只能改变一个字母。
  2. 转换过程中的每个中间单词必须在 wordList 中（注意：beginWord 不需要在 wordList 中，但 endWord 必须在）。
    如果不存在这样的转换序列，返回 0。

示例
输入：
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：最短转换序列是 "hit" → "hot" → "dot" → "dog" → "cog"，长度为 5。

解题过程循序渐进讲解

步骤 1：问题抽象与建模

这个问题本质上是在图中寻找两个节点之间的最短路径：

  • 每个单词是一个节点。
  • 如果两个单词之间恰好只有一个字母不同，则它们之间有一条无向边。
    目标：求从起点单词到终点单词的最短路径长度（边的数量）。
    注意：路径长度是转换次数，即节点数减 1，但题目要求返回的是节点数（序列长度）。

步骤 2：构建邻接关系的高效方法

如果直接两两比较所有单词是否只差一个字母，时间复杂度为 O(N²×L)，其中 N 是单词数量，L 是单词长度。当 N 较大时效率低。
优化思路：用“通配符”表示法来构建邻接关系。
例如单词 "hot" 可以转换成：

  • "*ot"：对应模式
  • "h*t"：对应模式
  • "ho*"：对应模式

具体做法：

  1. 遍历每个单词。
  2. 对单词的每个位置，用 '*' 替换该位置的字母，形成一个“模式”。
  3. 将原单词加入该模式对应的列表中。

这样，属于同一个模式的所有单词之间都只差一个字母，它们相互邻接。
用哈希表存储：键是模式字符串，值是属于该模式的所有单词列表。

步骤 3：广度优先搜索（BFS）找最短路径

BFS 是寻找无权图最短路径的标准算法。
算法步骤：

  1. 将 beginWord 加入队列，距离为 1（表示序列的第一个单词）。
  2. 从队列中取出一个单词，找出它的所有邻居（即所有与该单词只差一个字母的单词）。
  3. 如果邻居是 endWord，返回当前距离 + 1。
  4. 否则，如果邻居未被访问过，则标记为已访问，加入队列，距离为当前距离 + 1。
  5. 重复直到队列为空，如果未找到则返回 0。

关键细节：

  • 用集合 visited 记录已访问单词，避免重复访问。
  • 在 BFS 中，第一次遇到 endWord 时的路径一定是最短的。

步骤 4：具体实现步骤

  1. 预处理单词列表，构建模式哈希表：
    遍历 wordList 中的每个单词 word，对于每个位置 j（0 到 L-1），生成模式：word[:j] + '*' + word[j+1:]，将 word 加入该模式的列表中。
    例如对于 "hot"：

    • j=0: "*ot" → 列表中加入 "hot"
    • j=1: "h*t" → 列表中加入 "hot"
    • j=2: "ho*" → 列表中加入 "hot"

  2. BFS 过程：

    • 队列初始化：(beginWord, 1)
    • visited 初始化：{beginWord}
    • 每次从队列取出 (current_word, level)：
      a. 生成 current_word 的所有模式（同上）。
      b. 对每个模式，在哈希表中查找属于该模式的所有单词。
      c. 遍历这些邻居单词：
      • 如果邻居是 endWord，返回 level + 1。
      • 如果邻居未被访问，加入 visited 和队列，level + 1。
    • 如果队列空仍未找到，返回 0。

  3. 提前检查：
    如果 endWord 不在 wordList 中，直接返回 0。

步骤 5：示例推演

以示例说明：
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

  1. 构建模式哈希表（部分关键模式）：

    • "*ot" → ["hot", "dot", "lot"]
    • "h*t" → ["hot"]
    • "ho*" → ["hot"]
    • "d*t" → ["dot"]
    • "do*" → ["dot", "dog"]
    • "*og" → ["dog", "log", "cog"]
    • "d*g" → ["dog"]
    • "l*t" → ["lot"]
    • "lo*" → ["lot", "log"]
    • "l*g" → ["log"]
    • "c*g" → ["cog"]
    • "co*" → ["cog"]
    • 等等。

  2. BFS 过程：

    • 初始队列: [("hit", 1)]
    • 处理 "hit"：生成模式 "*it"、"h*t"、"hi*"，其中 "h*t" 对应 ["hot"]，所以邻居 "hot" 入队，level=2。
    • 处理 "hot"：生成模式 "*ot"、"h*t"、"ho*"。
      • 模式 "*ot" 对应 ["hot","dot","lot"]，邻居 "dot" 和 "lot" 入队，level=3。
      • 模式 "h*t" 对应 ["hot"]（已访问）。
      • 模式 "ho*" 对应 ["hot"]。
    • 处理 "dot"：模式 "*ot"（已访问过邻居），"d*t"（无其他单词），"do*" 对应 ["dot","dog"]，邻居 "dog" 入队，level=4。
    • 处理 "lot"：模式 "*ot"（已访问），"l*t"（无其他），"lo*" 对应 ["lot","log"]，邻居 "log" 入队，level=4。
    • 处理 "dog"：模式 "*og" 对应 ["dog","log","cog"]，发现 "cog" 是 endWord，返回当前 level=4 + 1 = 5。

结果：5。

步骤 6：复杂度分析

  • 设单词数量 N，单词长度 L。
  • 构建模式哈希表：O(N×L)（每个单词生成 L 个模式，哈希表插入 O(1)）。
  • BFS 过程：每个单词只会被访问一次，每次访问需要 O(L) 时间生成模式，并在哈希表中查找邻居（邻居总数为 O(N×L) 但均摊后每个单词访问时检查的邻居是有限的）。
  • 总时间复杂度：O(N×L²) 如果考虑字符串构建，但通常 L 较小，视为 O(N×L)。
  • 空间复杂度：O(N×L) 存储模式哈希表。

总结
单词接龙问题通过“模式哈希表”将找邻居的时间从 O(N×L) 降为 O(L)（生成模式并查表），再结合 BFS 找最短路径。哈希表在这里核心作用是高效地建立单词之间的邻接关系，避免两两比较。

单词接龙 题目描述 给你两个单词 beginWord 和 endWord ，以及一个单词列表 wordList 。你需要找到从 beginWord 到 endWord 的 最短转换序列 的长度，转换需遵循以下规则： 每次转换只能改变一个字母。 转换过程中的每个中间单词必须在 wordList 中（注意： beginWord 不需要在 wordList 中，但 endWord 必须在）。 如果不存在这样的转换序列，返回 0。 示例 输入： beginWord = "hit", endWord = "cog", wordList = [ "hot","dot","dog","lot","log","cog" ] 输出：5 解释：最短转换序列是 "hit" → "hot" → "dot" → "dog" → "cog"，长度为 5。 解题过程循序渐进讲解 步骤 1：问题抽象与建模 这个问题本质上是 在图中寻找两个节点之间的最短路径 ： 每个单词是一个节点。 如果两个单词之间 恰好只有一个字母不同 ，则它们之间有一条无向边。 目标：求从起点单词到终点单词的最短路径长度（边的数量）。 注意 ：路径长度是转换次数，即节点数减 1，但题目要求返回的是节点数（序列长度）。 步骤 2：构建邻接关系的高效方法 如果直接两两比较所有单词是否只差一个字母，时间复杂度为 O(N²×L)，其中 N 是单词数量，L 是单词长度。当 N 较大时效率低。 优化思路 ：用“通配符”表示法来构建邻接关系。 例如单词 "hot" 可以转换成： "* ot"：对应模式 "h* t"：对应模式 "ho* "：对应模式 具体做法 ： 遍历每个单词。 对单词的每个位置，用 '* ' 替换该位置的字母，形成一个“模式”。 将原单词加入该模式对应的列表中。 这样，属于同一个模式的所有单词之间都只差一个字母，它们相互邻接。 用 哈希表 存储：键是模式字符串，值是属于该模式的所有单词列表。 步骤 3：广度优先搜索（BFS）找最短路径 BFS 是寻找无权图最短路径的标准算法。 算法步骤 ： 将 beginWord 加入队列，距离为 1（表示序列的第一个单词）。 从队列中取出一个单词，找出它的所有邻居（即所有与该单词只差一个字母的单词）。 如果邻居是 endWord ，返回当前距离 + 1。 否则，如果邻居未被访问过，则标记为已访问，加入队列，距离为当前距离 + 1。 重复直到队列为空，如果未找到则返回 0。 关键细节 ： 用集合 visited 记录已访问单词，避免重复访问。 在 BFS 中，第一次遇到 endWord 时的路径一定是最短的。 步骤 4：具体实现步骤 预处理单词列表，构建模式哈希表 ： 遍历 wordList 中的每个单词 word ，对于每个位置 j（0 到 L-1），生成模式： word[:j] + '*' + word[j+1:] ，将 word 加入该模式的列表中。 例如对于 "hot"： j=0: "*ot" → 列表中加入 "hot" j=1: "h*t" → 列表中加入 "hot" j=2: "ho*" → 列表中加入 "hot" BFS 过程 ： 队列初始化： (beginWord, 1) visited 初始化： {beginWord} 每次从队列取出 (current_word, level) ： a. 生成 current_word 的所有模式（同上）。 b. 对每个模式，在哈希表中查找属于该模式的所有单词。 c. 遍历这些邻居单词： 如果邻居是 endWord ，返回 level + 1 。 如果邻居未被访问，加入 visited 和队列， level + 1 。 如果队列空仍未找到，返回 0。 提前检查 ： 如果 endWord 不在 wordList 中，直接返回 0。 步骤 5：示例推演 以示例说明： beginWord = "hit", endWord = "cog", wordList = [ "hot","dot","dog","lot","log","cog" ] 构建模式哈希表（部分关键模式）： "*ot" → [ "hot", "dot", "lot" ] "h*t" → [ "hot" ] "ho*" → [ "hot" ] "d*t" → [ "dot" ] "do*" → [ "dot", "dog" ] "*og" → [ "dog", "log", "cog" ] "d*g" → [ "dog" ] "l*t" → [ "lot" ] "lo*" → [ "lot", "log" ] "l*g" → [ "log" ] "c*g" → [ "cog" ] "co*" → [ "cog" ] 等等。 BFS 过程： 初始队列: [ ("hit", 1) ] 处理 "hit"：生成模式 "*it" 、 "h*t" 、 "hi*" ，其中 "h*t" 对应 [ "hot" ]，所以邻居 "hot" 入队，level=2。 处理 "hot"：生成模式 "*ot" 、 "h*t" 、 "ho*" 。 模式 "*ot" 对应 [ "hot","dot","lot" ]，邻居 "dot" 和 "lot" 入队，level=3。 模式 "h*t" 对应 [ "hot" ]（已访问）。 模式 "ho*" 对应 [ "hot" ]。 处理 "dot"：模式 "*ot" （已访问过邻居）， "d*t" （无其他单词）， "do*" 对应 [ "dot","dog" ]，邻居 "dog" 入队，level=4。 处理 "lot"：模式 "*ot" （已访问）， "l*t" （无其他）， "lo*" 对应 [ "lot","log" ]，邻居 "log" 入队，level=4。 处理 "dog"：模式 "*og" 对应 [ "dog","log","cog" ]，发现 "cog" 是 endWord，返回当前 level=4 + 1 = 5。 结果：5。 步骤 6：复杂度分析 设单词数量 N，单词长度 L。 构建模式哈希表：O(N×L)（每个单词生成 L 个模式，哈希表插入 O(1)）。 BFS 过程：每个单词只会被访问一次，每次访问需要 O(L) 时间生成模式，并在哈希表中查找邻居（邻居总数为 O(N×L) 但均摊后每个单词访问时检查的邻居是有限的）。 总时间复杂度：O(N×L²) 如果考虑字符串构建，但通常 L 较小，视为 O(N×L)。 空间复杂度：O(N×L) 存储模式哈希表。 总结 单词接龙问题通过“模式哈希表”将找邻居的时间从 O(N×L) 降为 O(L)（生成模式并查表），再结合 BFS 找最短路径。哈希表在这里核心作用是高效地建立单词之间的邻接关系，避免两两比较。