LeetCode 127: Word Ladder (BFS + Wildcard Pattern Graph)
LeetCode 127GraphBFSStringToday we solve LeetCode 127 - Word Ladder.
Source: https://leetcode.com/problems/word-ladder/
English
Problem Summary
Given beginWord, endWord, and a dictionary, return the length of the shortest transformation sequence from begin to end where each step changes exactly one character and every intermediate word must be in the dictionary.
Key Insight
This is an unweighted shortest-path problem on an implicit graph. Build adjacency quickly using wildcard patterns (e.g. h*t, *ot) so each BFS expansion can fetch one-letter neighbors in near-linear total time.
Brute Force and Why Insufficient
Checking every pair of words for one-character difference is O(N^2 * L), which is too expensive when the list is large. Wildcard indexing reduces repeated comparisons significantly.
Optimal Algorithm (Step-by-Step)
1) If endWord is not in dictionary, return 0.
2) Build a map: wildcard pattern -> all words matching that pattern.
3) Run BFS from beginWord with depth starting at 1.
4) For each popped word, generate its L patterns and traverse unseen neighbors from the map.
5) First time reaching endWord, return current depth + 1.
Complexity Analysis
Time: O(N * L^2) (pattern generation + BFS transitions).
Space: O(N * L) for wildcard buckets and visited set.
Common Pitfalls
- Forgetting the early return when endWord is absent.
- Revisiting words without a visited set (causes blowup/loops).
- Not including beginWord in pattern indexing path logic.
- Mixing level counting and queue operations, returning wrong ladder length.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
if (!dict.contains(endWord)) return 0;
int L = beginWord.length();
Map<String, List<String>> buckets = new HashMap<>();
for (String word : dict) {
for (int i = 0; i < L; i++) {
String key = word.substring(0, i) + '*' + word.substring(i + 1);
buckets.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
}
}
Queue<String> q = new ArrayDeque<>();
q.offer(beginWord);
Set<String> visited = new HashSet<>();
visited.add(beginWord);
int steps = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String cur = q.poll();
if (cur.equals(endWord)) return steps;
for (int j = 0; j < L; j++) {
String key = cur.substring(0, j) + '*' + cur.substring(j + 1);
for (String nxt : buckets.getOrDefault(key, Collections.emptyList())) {
if (visited.add(nxt)) q.offer(nxt);
}
}
}
steps++;
}
return 0;
}
}func ladderLength(beginWord string, endWord string, wordList []string) int {
dict := map[string]bool{}
for _, w := range wordList {
dict[w] = true
}
if !dict[endWord] {
return 0
}
L := len(beginWord)
buckets := map[string][]string{}
for w := range dict {
for i := 0; i < L; i++ {
key := w[:i] + "*" + w[i+1:]
buckets[key] = append(buckets[key], w)
}
}
q := []string{beginWord}
visited := map[string]bool{beginWord: true}
steps := 1
for len(q) > 0 {
sz := len(q)
for i := 0; i < sz; i++ {
cur := q[0]
q = q[1:]
if cur == endWord {
return steps
}
for j := 0; j < L; j++ {
key := cur[:j] + "*" + cur[j+1:]
for _, nxt := range buckets[key] {
if !visited[nxt] {
visited[nxt] = true
q = append(q, nxt)
}
}
}
}
steps++
}
return 0
}class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
if (!dict.count(endWord)) return 0;
int L = beginWord.size();
unordered_map<string, vector<string>> buckets;
for (const string& w : dict) {
for (int i = 0; i < L; ++i) {
string key = w.substr(0, i) + "*" + w.substr(i + 1);
buckets[key].push_back(w);
}
}
queue<string> q;
q.push(beginWord);
unordered_set<string> vis{beginWord};
int steps = 1;
while (!q.empty()) {
int sz = q.size();
while (sz--) {
string cur = q.front(); q.pop();
if (cur == endWord) return steps;
for (int i = 0; i < L; ++i) {
string key = cur.substr(0, i) + "*" + cur.substr(i + 1);
for (const string& nxt : buckets[key]) {
if (!vis.count(nxt)) {
vis.insert(nxt);
q.push(nxt);
}
}
}
}
++steps;
}
return 0;
}
};from collections import defaultdict, deque
from typing import List
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
word_set = set(wordList)
if endWord not in word_set:
return 0
L = len(beginWord)
buckets = defaultdict(list)
for w in word_set:
for i in range(L):
buckets[w[:i] + '*' + w[i + 1:]].append(w)
q = deque([beginWord])
visited = {beginWord}
steps = 1
while q:
for _ in range(len(q)):
cur = q.popleft()
if cur == endWord:
return steps
for i in range(L):
key = cur[:i] + '*' + cur[i + 1:]
for nxt in buckets[key]:
if nxt not in visited:
visited.add(nxt)
q.append(nxt)
steps += 1
return 0var ladderLength = function(beginWord, endWord, wordList) {
const dict = new Set(wordList);
if (!dict.has(endWord)) return 0;
const L = beginWord.length;
const buckets = new Map();
for (const w of dict) {
for (let i = 0; i < L; i++) {
const key = w.slice(0, i) + '*' + w.slice(i + 1);
if (!buckets.has(key)) buckets.set(key, []);
buckets.get(key).push(w);
}
}
const q = [beginWord];
const visited = new Set([beginWord]);
let steps = 1;
while (q.length) {
const size = q.length;
for (let i = 0; i < size; i++) {
const cur = q.shift();
if (cur === endWord) return steps;
for (let j = 0; j < L; j++) {
const key = cur.slice(0, j) + '*' + cur.slice(j + 1);
for (const nxt of (buckets.get(key) || [])) {
if (!visited.has(nxt)) {
visited.add(nxt);
q.push(nxt);
}
}
}
}
steps++;
}
return 0;
};中文
题目概述
给定 beginWord、endWord 和词典，每次只能改一个字符，且中间词必须在词典中，求从 begin 到 end 的最短转换序列长度。
核心思路
这是隐式图上的无权最短路问题。用通配模式（如 h*t、*ot）建立“词到邻居”的快速索引，再用 BFS 按层扩展即可得到最短步数。
暴力解法与不足
若每次都与所有单词逐个比较是否只差一个字符，复杂度接近 O(N^2 * L)，词典大时会明显超时。通配桶能显著减少重复比较。
最优算法（步骤）
1）若词典中不存在 endWord，直接返回 0。
2）为词典中的每个单词生成 L 个通配键，建立映射。
3）从 beginWord 开始做 BFS，层数初始化为 1。
4）弹出当前词后生成其通配键，访问所有未访问邻居。
5）首次到达 endWord 时返回当前层数。
复杂度分析
时间复杂度：O(N * L^2)。
空间复杂度：O(N * L)（通配桶 + 访问集）。
常见陷阱
- 忘记先判断 endWord 是否存在于词典。
- 未做 visited 去重，导致反复入队。
- 没理清层序计数，返回的长度偏 1。
- 只建单词直接邻接，不做模式索引，性能退化。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
if (!dict.contains(endWord)) return 0;
int L = beginWord.length();
Map<String, List<String>> buckets = new HashMap<>();
for (String word : dict) {
for (int i = 0; i < L; i++) {
String key = word.substring(0, i) + '*' + word.substring(i + 1);
buckets.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
}
}
Queue<String> q = new ArrayDeque<>();
q.offer(beginWord);
Set<String> visited = new HashSet<>();
visited.add(beginWord);
int steps = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String cur = q.poll();
if (cur.equals(endWord)) return steps;
for (int j = 0; j < L; j++) {
String key = cur.substring(0, j) + '*' + cur.substring(j + 1);
for (String nxt : buckets.getOrDefault(key, Collections.emptyList())) {
if (visited.add(nxt)) q.offer(nxt);
}
}
}
steps++;
}
return 0;
}
}func ladderLength(beginWord string, endWord string, wordList []string) int {
dict := map[string]bool{}
for _, w := range wordList {
dict[w] = true
}
if !dict[endWord] {
return 0
}
L := len(beginWord)
buckets := map[string][]string{}
for w := range dict {
for i := 0; i < L; i++ {
key := w[:i] + "*" + w[i+1:]
buckets[key] = append(buckets[key], w)
}
}
q := []string{beginWord}
visited := map[string]bool{beginWord: true}
steps := 1
for len(q) > 0 {
sz := len(q)
for i := 0; i < sz; i++ {
cur := q[0]
q = q[1:]
if cur == endWord {
return steps
}
for j := 0; j < L; j++ {
key := cur[:j] + "*" + cur[j+1:]
for _, nxt := range buckets[key] {
if !visited[nxt] {
visited[nxt] = true
q = append(q, nxt)
}
}
}
}
steps++
}
return 0
}class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
if (!dict.count(endWord)) return 0;
int L = beginWord.size();
unordered_map<string, vector<string>> buckets;
for (const string& w : dict) {
for (int i = 0; i < L; ++i) {
string key = w.substr(0, i) + "*" + w.substr(i + 1);
buckets[key].push_back(w);
}
}
queue<string> q;
q.push(beginWord);
unordered_set<string> vis{beginWord};
int steps = 1;
while (!q.empty()) {
int sz = q.size();
while (sz--) {
string cur = q.front(); q.pop();
if (cur == endWord) return steps;
for (int i = 0; i < L; ++i) {
string key = cur.substr(0, i) + "*" + cur.substr(i + 1);
for (const string& nxt : buckets[key]) {
if (!vis.count(nxt)) {
vis.insert(nxt);
q.push(nxt);
}
}
}
}
++steps;
}
return 0;
}
};from collections import defaultdict, deque
from typing import List
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
word_set = set(wordList)
if endWord not in word_set:
return 0
L = len(beginWord)
buckets = defaultdict(list)
for w in word_set:
for i in range(L):
buckets[w[:i] + '*' + w[i + 1:]].append(w)
q = deque([beginWord])
visited = {beginWord}
steps = 1
while q:
for _ in range(len(q)):
cur = q.popleft()
if cur == endWord:
return steps
for i in range(L):
key = cur[:i] + '*' + cur[i + 1:]
for nxt in buckets[key]:
if nxt not in visited:
visited.add(nxt)
q.append(nxt)
steps += 1
return 0var ladderLength = function(beginWord, endWord, wordList) {
const dict = new Set(wordList);
if (!dict.has(endWord)) return 0;
const L = beginWord.length;
const buckets = new Map();
for (const w of dict) {
for (let i = 0; i < L; i++) {
const key = w.slice(0, i) + '*' + w.slice(i + 1);
if (!buckets.has(key)) buckets.set(key, []);
buckets.get(key).push(w);
}
}
const q = [beginWord];
const visited = new Set([beginWord]);
let steps = 1;
while (q.length) {
const size = q.length;
for (let i = 0; i < size; i++) {
const cur = q.shift();
if (cur === endWord) return steps;
for (let j = 0; j < L; j++) {
const key = cur.slice(0, j) + '*' + cur.slice(j + 1);
for (const nxt of (buckets.get(key) || [])) {
if (!visited.has(nxt)) {
visited.add(nxt);
q.push(nxt);
}
}
}
}
steps++;
}
return 0;
};
Comments