LeetCode 126. 单词接龙 II
题目描述
题意分析
从
beginWord出发，每一步恰好修改一个字母，并且修改后的单词必须存在于词表，最终到达endWord。需要返回全部最短转换序列，每条序列都包含起点与终点。起点不必在词表中，终点必须在词表中；没有合法路径时返回空列表。这里既要保证转换步数最少，也要保留相同步数下的全部方案，不能只记录一条路径或只返回长度。
解法：BFS 分层 + 回溯输出
核心思路
[!blue]
把单词看成节点，能够改一个字母互相转换的词之间有一条边，每条边都代表一步。BFS 按步数逐层访问，第一次到达终点的层数就是最短距离；但仅保存一个前驱无法还原所有最短路径，因此为每个新词记录全部最短前驱。
处理距离为
d的当前层时，visited已包含距离不超过d的词。合法邻词若尚未在visited中，其最短距离就是d + 1，将当前词加入parents[next]。这个邻词可能被本层多个节点找到，它们都应成为有效前驱。为同时保证前驱完整和队列去重，下一层新词先放入
nextLevel：每次找到它都记录前驱，但只有第一次加入nextLevel才安排入队。整层结束后再把这些词合入全局visited，下一轮便不会接受来自同层或更深处的无效回边。首次发现终点后不能立刻跳出当前层，其他当前层节点仍可能是它的最短前驱。只记录找到标志，将整层处理完，再停止向更深层搜索。
从终点沿前驱关系回溯，每走一步距离都减一，所以关系图无环，而且回到起点时得到的一定是最短路径。遍历每个前驱分支即可输出所有方案；保存时复制路径，Java 从头部补前驱，Go 在终点路径收集时反转复制，最终都按起点到终点返回。
解题步骤
- 建立词表集合，终点不在词表中时直接返回空结果。
- 起点入队并加入
visited，创建前驱表。- 每轮固定当前层，从各单词逐位尝试替换为其他小写字母，生成一步可达候选；处理完某一位后恢复原字母。
- 候选在词表且未被旧层访问时，记录当前词为前驱；本层第一次发现它才入队。
- 整层结束后合并
nextLevel到visited；本层已经发现终点则停止继续 BFS。- 未找到终点返回空结果；找到后，从终点沿全部前驱回溯到起点，复制每条完整路径。
代码实现
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> dictionary = new HashSet<>(wordList);
List<List<String>> answer = new ArrayList<>();
if (!dictionary.contains(endWord)) {
return answer;
}
Map<String, List<String>> parents = new HashMap<>();
Queue<String> queue = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
queue.offer(beginWord);
visited.add(beginWord);
boolean found = false;
while (!queue.isEmpty() && !found) {
int levelSize = queue.size();
// 本轮新发现的下一层单词暂存此处，层末再统一标记。
Set<String> nextLevel = new HashSet<>();
for (int count = 0; count < levelSize; count++) {
String word = queue.poll();
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; i++) {
char original = chars[i];
for (char letter = 'a'; letter <= 'z'; letter++) {
if (letter == original) {
continue;
}
chars[i] = letter;
String next = new String(chars);
if (!dictionary.contains(next) || visited.contains(next)) {
continue;
}
// 每个最短前驱都记录，与是否首次入队分开处理。
parents.computeIfAbsent(next, key -> new ArrayList<>()).add(word);
// 下一层单词只入队一次，但可以拥有多个本层前驱。
if (nextLevel.add(next)) {
queue.offer(next);
}
// 只记录找到终点，仍继续收齐本层其他最短前驱。
if (next.equals(endWord)) {
found = true;
}
}
// 恢复当前修改位置，再尝试修改下一个位置。
chars[i] = original;
}
}
// 整层完成后才合入全局访问集合。
visited.addAll(nextLevel);
}
if (!found) {
return answer;
}
Deque<String> path = new ArrayDeque<>();
path.addFirst(endWord);
buildPaths(endWord, beginWord, parents, path, answer);
return answer;
}
private void buildPaths(
String word,
String beginWord,
Map<String, List<String>> parents,
Deque<String> path,
List<List<String>> answer) {
if (word.equals(beginWord)) {
// 保存路径副本，后续回溯不会修改已完成答案。
answer.add(new ArrayList<>(path));
return;
}
for (String parent : parents.getOrDefault(word, List.of())) {
path.addFirst(parent);
buildPaths(parent, beginWord, parents, path, answer);
// 撤销当前前驱，继续枚举另一条最短路径。
path.removeFirst();
}
}
}
func findLadders(beginWord string, endWord string, wordList []string) [][]string {
dictionary := make(map[string]struct{}, len(wordList))
for _, word := range wordList {
dictionary[word] = struct{}{}
}
if _, exists := dictionary[endWord]; !exists {
return [][]string{}
}
parents := make(map[string][]string)
visited := map[string]struct{}{beginWord: {}}
queue := []string{
beginWord,
}
found := false
for len(queue) > 0 && !found {
currentLevel := queue
queue = nil
// 本轮新发现的下一层单词暂存此处，层末再统一标记。
nextLevel := make(map[string]struct{})
for _, word := range currentLevel {
chars := []byte(word)
for i := range chars {
original := chars[i]
for letter := byte('a'); letter <= byte('z'); letter++ {
if letter == original {
continue
}
chars[i] = letter
next := string(chars)
if _, exists := dictionary[next]; !exists {
continue
}
if _, exists := visited[next]; exists {
continue
}
// 每个最短前驱都记录，与是否首次入队分开处理。
parents[next] = append(parents[next], word)
// 下一层单词只入队一次，但可以拥有多个本层前驱。
if _, exists := nextLevel[next]; !exists {
nextLevel[next] = struct{}{}
queue = append(queue, next)
}
// 只记录找到终点，仍继续收齐本层其他最短前驱。
if next == endWord {
found = true
}
}
// 恢复当前修改位置，再尝试修改下一个位置。
chars[i] = original
}
}
// 整层完成后才合入全局访问集合。
for word := range nextLevel {
visited[word] = struct{}{}
}
}
if !found {
return [][]string{}
}
answer := make([][]string, 0)
path := []string{
endWord,
}
buildPaths126(endWord, beginWord, parents, path, &answer)
return answer
}
func buildPaths126(
word string,
beginWord string,
parents map[string][]string,
path []string,
answer *[][]string,
) {
if word == beginWord {
// 反转复制当前路径，不能直接保存随后会回溯的切片。
sequence := make([]string, len(path))
for i := range path {
sequence[len(path)-1-i] = path[i]
}
*answer = append(*answer, sequence)
return
}
for _, parent := range parents[word] {
path = append(path, parent)
buildPaths126(parent, beginWord, parents, path, answer)
// 撤销当前前驱，继续枚举另一条最短路径。
path = path[:len(path)-1]
}
}
复杂度分析
- 时间复杂度：期望 $O((N+1)L^2+PD)$，
N为词表大小、L为词长、P为答案路径数、D为每条最短路径的单词数。每个被展开的词有 $O(26L)$ 个候选，每次构造和哈希最多处理L个字符；回溯和复制全部结果需要 $O(PD)$。- 空间复杂度：辅助空间为 $O(NL+E+D)$，
E为保存的前驱边数，集合及生成单词保存线性数量的词，回溯深度为D；输出路径列表另占 $O(PD)$，其中单词字符串可共享。
关键点总结
[!green]
- BFS 确定最短距离，前驱图保留最短路径的所有选择，回溯负责输出。
- 多个前驱都要保存，一个下一层单词只需入队一次，两种去重目标不能混淆。
- 全局访问标记延迟到层末，才能保留同层不同来源。
- 发现终点后处理完整层，随后无需扩展更深节点。
- 前驱边严格向浅层移动，回溯自然不会走环或生成更长路径。
易错点总结
[!yellow]
- 一个候选刚发现就加入全局
visited，本层其他节点再遇到它时会被跳过，丢失最短前驱。- 将保存前驱放在首次入队的分支内，同样只能留下第一个来源。
- 首次发现终点就立刻返回，尚未处理的同层节点可能提供其他最短方案。
- 不区分旧层与下一层，任意邻接边都加入前驱图，会引入回边或非最短路径。
- 修改一个字母后不恢复，下一位置的候选可能同时改变多位，变成非法转换。
- 直接保存可变路径，后续撤销会改变旧答案；Go 从终点回溯的路径还需反转后保存。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 127. 单词接龙 | 困难 | 最短距离搜索相同，本题还需保留全部最短前驱关系并回溯输出路径。 |
| 797. 所有可能的路径 | 中等 | 同样枚举DAG中的路径，单词题可先用BFS层数过滤只属于最短路的有向边。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！