LeetCode 126: Word Ladder II (Layered BFS + Parent DAG Backtracking)
LeetCode 126GraphBFSToday we solve LeetCode 126 - Word Ladder II.
Source: https://leetcode.com/problems/word-ladder-ii/
English
Problem Summary
Given beginWord, endWord, and a dictionary, return all shortest transformation sequences where each step changes exactly one character and each intermediate word must exist in the dictionary.
Key Insight
Use BFS by levels to guarantee shortest distance. Instead of storing only one predecessor, store all parents that reach a node at the same shortest level. This naturally forms a shortest-path DAG from endWord back to beginWord.
Brute Force and Limitations
Brute force DFS over all possible one-letter transformations explodes combinatorially. It revisits many states and cannot enforce shortest-only paths efficiently.
Optimal Algorithm Steps
1) Put all dictionary words in a hash set for O(1) lookup.
2) BFS from beginWord; for each word generate neighbors by changing each character to a..z.
3) Maintain dist[word] (shortest level) and parents[word] (all previous words on shortest paths).
4) Continue BFS until finishing the level where endWord first appears.
5) Backtrack from endWord to beginWord through parents to enumerate all shortest sequences.
Complexity Analysis
Let N be dictionary size and L word length.
BFS neighbor generation is roughly O(N * L * 26); backtracking cost is proportional to number of shortest answers.
Common Pitfalls
- Stopping BFS immediately when first seeing endWord inside a level (must finish that level).
- Keeping only one parent and losing valid shortest sequences.
- Globally marking visited too early and preventing same-level alternative parents.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
List<List<String>> ans = new ArrayList<>();
if (!dict.contains(endWord)) return ans;
Map<String, List<String>> parents = new HashMap<>();
Map<String, Integer> dist = new HashMap<>();
Queue<String> q = new LinkedList<>();
q.offer(beginWord);
dist.put(beginWord, 0);
int L = beginWord.length();
boolean found = false;
while (!q.isEmpty() && !found) {
int size = q.size();
for (int s = 0; s < size; s++) {
String cur = q.poll();
int d = dist.get(cur);
char[] arr = cur.toCharArray();
for (int i = 0; i < L; i++) {
char old = arr[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == old) continue;
arr[i] = c;
String nxt = new String(arr);
if (!dict.contains(nxt)) continue;
if (!dist.containsKey(nxt)) {
dist.put(nxt, d + 1);
q.offer(nxt);
parents.computeIfAbsent(nxt, k -> new ArrayList<>()).add(cur);
} else if (dist.get(nxt) == d + 1) {
parents.get(nxt).add(cur);
}
if (nxt.equals(endWord)) found = true;
}
arr[i] = old;
}
}
}
if (!dist.containsKey(endWord)) return ans;
LinkedList<String> path = new LinkedList<>();
path.add(endWord);
dfs(endWord, beginWord, parents, path, ans);
return ans;
}
private void dfs(String cur, String beginWord, Map<String, List<String>> parents,
LinkedList<String> path, List<List<String>> ans) {
if (cur.equals(beginWord)) {
List<String> one = new ArrayList<>(path);
Collections.reverse(one);
ans.add(one);
return;
}
if (!parents.containsKey(cur)) return;
for (String p : parents.get(cur)) {
path.addLast(p);
dfs(p, beginWord, parents, path, ans);
path.removeLast();
}
}
}func findLadders(beginWord string, endWord string, wordList []string) [][]string {
dict := map[string]bool{}
for _, w := range wordList {
dict[w] = true
}
if !dict[endWord] {
return [][]string{}
}
parents := map[string][]string{}
dist := map[string]int{beginWord: 0}
q := []string{beginWord}
found := false
L := len(beginWord)
for len(q) > 0 && !found {
size := len(q)
for s := 0; s < size; s++ {
cur := q[0]
q = q[1:]
d := dist[cur]
b := []byte(cur)
for i := 0; i < L; i++ {
old := b[i]
for c := byte('a'); c <= byte('z'); c++ {
if c == old {
continue
}
b[i] = c
nxt := string(b)
if !dict[nxt] {
continue
}
if _, ok := dist[nxt]; !ok {
dist[nxt] = d + 1
q = append(q, nxt)
parents[nxt] = append(parents[nxt], cur)
} else if dist[nxt] == d+1 {
parents[nxt] = append(parents[nxt], cur)
}
if nxt == endWord {
found = true
}
}
b[i] = old
}
}
}
if _, ok := dist[endWord]; !ok {
return [][]string{}
}
ans := [][]string{}
path := []string{endWord}
var dfs func(string)
dfs = func(cur string) {
if cur == beginWord {
one := make([]string, len(path))
for i := range path {
one[i] = path[len(path)-1-i]
}
ans = append(ans, one)
return
}
for _, p := range parents[cur] {
path = append(path, p)
dfs(p)
path = path[:len(path)-1]
}
}
dfs(endWord)
return ans
}class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
vector<vector<string>> ans;
if (!dict.count(endWord)) return ans;
unordered_map<string, vector<string>> parents;
unordered_map<string, int> dist;
queue<string> q;
q.push(beginWord);
dist[beginWord] = 0;
bool found = false;
int L = beginWord.size();
while (!q.empty() && !found) {
int size = q.size();
while (size--) {
string cur = q.front(); q.pop();
int d = dist[cur];
string nxt = cur;
for (int i = 0; i < L; i++) {
char old = nxt[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == old) continue;
nxt[i] = c;
if (!dict.count(nxt)) continue;
if (!dist.count(nxt)) {
dist[nxt] = d + 1;
q.push(nxt);
parents[nxt].push_back(cur);
} else if (dist[nxt] == d + 1) {
parents[nxt].push_back(cur);
}
if (nxt == endWord) found = true;
}
nxt[i] = old;
}
}
}
if (!dist.count(endWord)) return ans;
vector<string> path{endWord};
function<void(const string&)> dfs = [&](const string& cur) {
if (cur == beginWord) {
vector<string> one(path.rbegin(), path.rend());
ans.push_back(one);
return;
}
if (!parents.count(cur)) return;
for (const string& p : parents[cur]) {
path.push_back(p);
dfs(p);
path.pop_back();
}
};
dfs(endWord);
return ans;
}
};from collections import defaultdict, deque
from typing import List
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
dict_set = set(wordList)
if endWord not in dict_set:
return []
parents = defaultdict(list)
dist = {beginWord: 0}
q = deque([beginWord])
L = len(beginWord)
found = False
while q and not found:
for _ in range(len(q)):
cur = q.popleft()
d = dist[cur]
arr = list(cur)
for i in range(L):
old = arr[i]
for c in "abcdefghijklmnopqrstuvwxyz":
if c == old:
continue
arr[i] = c
nxt = "".join(arr)
if nxt not in dict_set:
continue
if nxt not in dist:
dist[nxt] = d + 1
q.append(nxt)
parents[nxt].append(cur)
elif dist[nxt] == d + 1:
parents[nxt].append(cur)
if nxt == endWord:
found = True
arr[i] = old
if endWord not in dist:
return []
ans = []
path = [endWord]
def dfs(cur: str) -> None:
if cur == beginWord:
ans.append(path[::-1])
return
for p in parents[cur]:
path.append(p)
dfs(p)
path.pop()
dfs(endWord)
return ans/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {string[][]}
*/
var findLadders = function(beginWord, endWord, wordList) {
const dict = new Set(wordList);
if (!dict.has(endWord)) return [];
const parents = new Map();
const dist = new Map([[beginWord, 0]]);
const q = [beginWord];
const L = beginWord.length;
let found = false;
while (q.length && !found) {
const size = q.length;
for (let s = 0; s < size; s++) {
const cur = q.shift();
const d = dist.get(cur);
const arr = cur.split('');
for (let i = 0; i < L; i++) {
const old = arr[i];
for (let code = 97; code <= 122; code++) {
const c = String.fromCharCode(code);
if (c === old) continue;
arr[i] = c;
const nxt = arr.join('');
if (!dict.has(nxt)) continue;
if (!dist.has(nxt)) {
dist.set(nxt, d + 1);
q.push(nxt);
if (!parents.has(nxt)) parents.set(nxt, []);
parents.get(nxt).push(cur);
} else if (dist.get(nxt) === d + 1) {
parents.get(nxt).push(cur);
}
if (nxt === endWord) found = true;
}
arr[i] = old;
}
}
}
if (!dist.has(endWord)) return [];
const ans = [];
const path = [endWord];
const dfs = (cur) => {
if (cur === beginWord) {
ans.push([...path].reverse());
return;
}
const ps = parents.get(cur) || [];
for (const p of ps) {
path.push(p);
dfs(p);
path.pop();
}
};
dfs(endWord);
return ans;
};中文
题目概述
给定 beginWord、endWord 和词典，要求找出所有最短转换序列。每一步只能改一个字符，且中间词必须在词典中。
核心思路
按层 BFS 才能保证“最短步数”。同时记录每个单词在最短层级下可能的所有前驱（parents），最终形成一张最短路径 DAG，再从 endWord 逆向回溯出全部答案。
基线解法与不足
如果直接 DFS 穷举所有变换路径，分支数会快速爆炸，而且很难只保留最短路径，性能和正确性都不稳定。
最优算法步骤
1）词典放入哈希集合，支持 O(1) 判断。
2）从 beginWord 做分层 BFS，枚举每一位替换成 a..z 生成邻居。
3）维护 dist（最短层数）和 parents（所有最短前驱）。
4）当某层首次触达 endWord 时，仍要把这一层处理完。
5）从 endWord 沿 parents 回溯到 beginWord，得到所有最短序列。
复杂度分析
设词典大小为 N，单词长度为 L。BFS 邻居生成约为 O(N * L * 26)；回溯成本与最短答案条数成正比。
常见陷阱
- 在层内第一次遇到 endWord 就立刻退出，导致漏解。
- 只记录一个前驱，导致不能枚举全部最短路径。
- visited 标记时机错误，屏蔽了同层的等长前驱。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
List<List<String>> ans = new ArrayList<>();
if (!dict.contains(endWord)) return ans;
Map<String, List<String>> parents = new HashMap<>();
Map<String, Integer> dist = new HashMap<>();
Queue<String> q = new LinkedList<>();
q.offer(beginWord);
dist.put(beginWord, 0);
int L = beginWord.length();
boolean found = false;
while (!q.isEmpty() && !found) {
int size = q.size();
for (int s = 0; s < size; s++) {
String cur = q.poll();
int d = dist.get(cur);
char[] arr = cur.toCharArray();
for (int i = 0; i < L; i++) {
char old = arr[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == old) continue;
arr[i] = c;
String nxt = new String(arr);
if (!dict.contains(nxt)) continue;
if (!dist.containsKey(nxt)) {
dist.put(nxt, d + 1);
q.offer(nxt);
parents.computeIfAbsent(nxt, k -> new ArrayList<>()).add(cur);
} else if (dist.get(nxt) == d + 1) {
parents.get(nxt).add(cur);
}
if (nxt.equals(endWord)) found = true;
}
arr[i] = old;
}
}
}
if (!dist.containsKey(endWord)) return ans;
LinkedList<String> path = new LinkedList<>();
path.add(endWord);
dfs(endWord, beginWord, parents, path, ans);
return ans;
}
private void dfs(String cur, String beginWord, Map<String, List<String>> parents,
LinkedList<String> path, List<List<String>> ans) {
if (cur.equals(beginWord)) {
List<String> one = new ArrayList<>(path);
Collections.reverse(one);
ans.add(one);
return;
}
if (!parents.containsKey(cur)) return;
for (String p : parents.get(cur)) {
path.addLast(p);
dfs(p, beginWord, parents, path, ans);
path.removeLast();
}
}
}func findLadders(beginWord string, endWord string, wordList []string) [][]string {
dict := map[string]bool{}
for _, w := range wordList {
dict[w] = true
}
if !dict[endWord] {
return [][]string{}
}
parents := map[string][]string{}
dist := map[string]int{beginWord: 0}
q := []string{beginWord}
found := false
L := len(beginWord)
for len(q) > 0 && !found {
size := len(q)
for s := 0; s < size; s++ {
cur := q[0]
q = q[1:]
d := dist[cur]
b := []byte(cur)
for i := 0; i < L; i++ {
old := b[i]
for c := byte('a'); c <= byte('z'); c++ {
if c == old {
continue
}
b[i] = c
nxt := string(b)
if !dict[nxt] {
continue
}
if _, ok := dist[nxt]; !ok {
dist[nxt] = d + 1
q = append(q, nxt)
parents[nxt] = append(parents[nxt], cur)
} else if dist[nxt] == d+1 {
parents[nxt] = append(parents[nxt], cur)
}
if nxt == endWord {
found = true
}
}
b[i] = old
}
}
}
if _, ok := dist[endWord]; !ok {
return [][]string{}
}
ans := [][]string{}
path := []string{endWord}
var dfs func(string)
dfs = func(cur string) {
if cur == beginWord {
one := make([]string, len(path))
for i := range path {
one[i] = path[len(path)-1-i]
}
ans = append(ans, one)
return
}
for _, p := range parents[cur] {
path = append(path, p)
dfs(p)
path = path[:len(path)-1]
}
}
dfs(endWord)
return ans
}class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
vector<vector<string>> ans;
if (!dict.count(endWord)) return ans;
unordered_map<string, vector<string>> parents;
unordered_map<string, int> dist;
queue<string> q;
q.push(beginWord);
dist[beginWord] = 0;
bool found = false;
int L = beginWord.size();
while (!q.empty() && !found) {
int size = q.size();
while (size--) {
string cur = q.front(); q.pop();
int d = dist[cur];
string nxt = cur;
for (int i = 0; i < L; i++) {
char old = nxt[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == old) continue;
nxt[i] = c;
if (!dict.count(nxt)) continue;
if (!dist.count(nxt)) {
dist[nxt] = d + 1;
q.push(nxt);
parents[nxt].push_back(cur);
} else if (dist[nxt] == d + 1) {
parents[nxt].push_back(cur);
}
if (nxt == endWord) found = true;
}
nxt[i] = old;
}
}
}
if (!dist.count(endWord)) return ans;
vector<string> path{endWord};
function<void(const string&)> dfs = [&](const string& cur) {
if (cur == beginWord) {
vector<string> one(path.rbegin(), path.rend());
ans.push_back(one);
return;
}
if (!parents.count(cur)) return;
for (const string& p : parents[cur]) {
path.push_back(p);
dfs(p);
path.pop_back();
}
};
dfs(endWord);
return ans;
}
};from collections import defaultdict, deque
from typing import List
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
dict_set = set(wordList)
if endWord not in dict_set:
return []
parents = defaultdict(list)
dist = {beginWord: 0}
q = deque([beginWord])
L = len(beginWord)
found = False
while q and not found:
for _ in range(len(q)):
cur = q.popleft()
d = dist[cur]
arr = list(cur)
for i in range(L):
old = arr[i]
for c in "abcdefghijklmnopqrstuvwxyz":
if c == old:
continue
arr[i] = c
nxt = "".join(arr)
if nxt not in dict_set:
continue
if nxt not in dist:
dist[nxt] = d + 1
q.append(nxt)
parents[nxt].append(cur)
elif dist[nxt] == d + 1:
parents[nxt].append(cur)
if nxt == endWord:
found = True
arr[i] = old
if endWord not in dist:
return []
ans = []
path = [endWord]
def dfs(cur: str) -> None:
if cur == beginWord:
ans.append(path[::-1])
return
for p in parents[cur]:
path.append(p)
dfs(p)
path.pop()
dfs(endWord)
return ans/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {string[][]}
*/
var findLadders = function(beginWord, endWord, wordList) {
const dict = new Set(wordList);
if (!dict.has(endWord)) return [];
const parents = new Map();
const dist = new Map([[beginWord, 0]]);
const q = [beginWord];
const L = beginWord.length;
let found = false;
while (q.length && !found) {
const size = q.length;
for (let s = 0; s < size; s++) {
const cur = q.shift();
const d = dist.get(cur);
const arr = cur.split('');
for (let i = 0; i < L; i++) {
const old = arr[i];
for (let code = 97; code <= 122; code++) {
const c = String.fromCharCode(code);
if (c === old) continue;
arr[i] = c;
const nxt = arr.join('');
if (!dict.has(nxt)) continue;
if (!dist.has(nxt)) {
dist.set(nxt, d + 1);
q.push(nxt);
if (!parents.has(nxt)) parents.set(nxt, []);
parents.get(nxt).push(cur);
} else if (dist.get(nxt) === d + 1) {
parents.get(nxt).push(cur);
}
if (nxt === endWord) found = true;
}
arr[i] = old;
}
}
}
if (!dist.has(endWord)) return [];
const ans = [];
const path = [endWord];
const dfs = (cur) => {
if (cur === beginWord) {
ans.push([...path].reverse());
return;
}
const ps = parents.get(cur) || [];
for (const p of ps) {
path.push(p);
dfs(p);
path.pop();
}
};
dfs(endWord);
return ans;
};
Comments