type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定两个单词
beginWord和endWord，以及一个字典 wordList 。从单词
beginWord转化到单词endWord，转化序列为beginWord -> s1 -> s2 -> ... -> sk，需要满足：- 每对相邻的单词之间仅有单个字母不同。
- 转换过程中的每个单词
si（1 <= i <= k）必须是字典wordList中的单词。 其中beginWord不必是字典wordList中的单词，sk == endWord。
返回所有从
beginWord转化到endWord的最短转换序列，如果不存在这样的转换序列，返回一个空列表。
示例 1：
示例 2：
说明：
1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 500
wordList[i].length == beginWord.length
beginWord、endWord和wordList[i]由小写英文字母组成
beginWord != endWord
wordList中的所有单词 互不相同
解法一：BFS + DFS
- BFS 建距离表 + 记录前驱
- 从
beginWord开始进行 BFS； - 用
dist[word]记录从起点到该单词的层数； - 用
prev[word]记录可以通向该单词的“前驱单词”（上一层的节点）； - 一旦找到
endWord，说明已经到达最短层，可以停止 BFS。
- DFS 回溯所有路径
- 从
endWord反向追溯； - 每次通过
prev[word]找到所有可能的上一步； - 递归展开所有路径，直到回到起点。
最终我们得到所有的最短路径组合。
复杂度
- 时间：O(N × L²)
N是单词数量，L是单词长度；- 每次 BFS 需要替换
L个位置、尝试 26 个字母； - 实际平均会低于理论上限，因为单词过滤后减少。
- 空间：O(N × L)
- 主要用于字典映射、
prev记录前驱关系以及队列。
解法二：预处理邻接表 + BFS
上面的写法是边搜索边生成相邻单词，也可以提前把所有相邻关系存好。
对输入的单词做预处理：给每一个单词的每一位分别变成一个下划线。
例如
hot 变成：
- _ot
- h_t
- ho_这样可以很轻易地找到从每一个单词可以换到哪些单词。 如
hot 的 _ot 映射下能找到 lot 和 dot。这种方式适合字典很大的场景，因为只构建一次邻接表。
具体做法：
- 遍历字典，按 mask 模式（
_ot,h_t,ho_）分组；
- BFS用于找到最短转换路径，可以直接通过 mask 找所有邻居；
- 同样记录
prev表；
- 最后 DFS 回溯所有路径。
复杂度
- 时间：O(N × L²)
N为字典长度，L为单词长度；- 每个单词生成
L个 mask； - BFS 访问每个单词一次。
- 空间：O(N × L)
- 存储 mask 映射和
prev关系。
解法三：双向 BFS + 回溯（最优解）
BFS 的瓶颈在于搜索空间太大，而我们知道起点和终点。
双向 BFS 可以从两端同时扩展，可以显著减半搜索层数。
- 从两边出发：
begin_set与end_set；
- 每次扩展较小的一边；
- 记录相邻关系；
- 当两边相遇时，说明找到最短路径；
- 最后仍然 DFS 回溯所有路径。
复杂度
- 时间：
O(N × L)，比单向 BFS 更快；
- 空间：
O(N × L)。
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-126-单词接龙-ii
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 124] 二叉树中的最大路径和
下一篇
[Leetcode 128] 最长连续序列