LeetCode 126. 单词接龙 II

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

1. 每次转换只能改变一个字母。
2. 转换过程中的中间单词必须是字典 wordList 中的单词（包括 endWord，但不包括 beginWord，除非 beginWord 在字典中）。

如果无法完成转换，返回空列表。注意：字典中可能存在重复的单词，但序列中不能有重复的单词。

示例
输入：
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
输出：

[  
  ["hit","hot","dot","dog","cog"],  
  ["hit","hot","lot","log","cog"]  
]  

解题过程

步骤1：问题分析

• 本题是 LeetCode 127（单词接龙）的扩展，要求输出所有最短路径，而非仅路径长度。
• 难点在于：直接使用 BFS 会超时（因为需要记录路径），且需避免重复探索。
• 核心思路：
  1. 使用 BFS 构建从 endWord 到 beginWord 的层级关系（邻接表），记录每个单词的可达前驱单词。
  2. 使用 DFS（回溯）根据邻接表从 beginWord 反向构建路径到 endWord。

步骤2：预处理——构建通用单词模式

• 将每个单词（如 "hot"）转换为通用模式（如 "h*t", "*ot", "ho*"），建立“模式 → 实际单词”的映射。
• 例如："hot" 的模式为 ["*ot", "h*t", "ho*"]。
• 目的：快速找到只差一个字母的相邻单词。

步骤3：BFS 构建邻接表

• 从 endWord 开始 BFS（反向搜索），记录每个单词的层级（距离 endWord 的最短步数）。
• 邻接表 prevMap 记录每个单词的前驱单词列表（即哪些单词可以一步转换到当前单词）。
• 关键细节：
  • 遇到新单词时，将其加入队列并记录层级。
  • 若单词已存在且当前层级与其层级相同，则将其加入前驱列表（允许同一层级的多条路径）。
  • 一旦遇到 beginWord，停止 BFS（保证只探索最短路径范围内的单词）。

步骤4：DFS 回溯生成路径

• 从 beginWord 开始 DFS，根据 prevMap 逐层向下搜索到 endWord。
• 路径保存到结果列表时，需反转（因为邻接表是反向构建的）。
• 优化：使用 currPath 记录当前路径，避免重复访问（路径本身不会重复单词）。

步骤5：完整代码逻辑

1. 检查 endWord 是否在 wordList 中，否则返回空列表。
2. 预处理构建模式字典 patternMap。
3. BFS 初始化：队列包含 endWord，层级为 0，prevMap[endWord] 为空列表。
4. BFS 遍历：
   • 对当前单词生成所有模式，找到相邻单词。
   • 若相邻单词是 beginWord，直接记录前驱关系并标记找到最短路径。
   • 若相邻单词未访问过或处于同一层级，更新 prevMap。
5. DFS 回溯：从 beginWord 递归到 endWord，保存完整路径。

为什么这样做？

• BFS 保证找到最短路径，DFS 保证遍历所有可能路径。
• 反向 BFS 减少搜索空间（从终点开始，避免无效分支）。
• 邻接表避免重复计算，确保时间复杂度可控。

复杂度分析

• 时间复杂度：O(N × L²)，其中 N 是单词数，L 是单词长度（构建模式字典和 BFS 遍历）。
• 空间复杂度：O(N × L)（存储邻接表和路径）。

通过以上步骤，即可高效找出所有最短转换序列。