#89 · Graphs
Given beginWord, endWord and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, where each step changes exactly one letter and every intermediate word is in wordList; return 0 if none exists.
Pointers
Variables
Hash map / table
Stack / queue
Words are nodes; two words are adjacent if they differ in one letter. The graph is never built explicitly. BFS visits words in order of distance, so the first time it reaches endWord it has found the shortest ladder.
Memory layout
A FIFO queue of words (with their distance) and a visited set of at most N words.
| Operation | Cost |
|---|---|
| BFS visit | O(N) nodes, each with cost of finding neighbours |
Each word of length L contributes L patterns with one letter replaced by * ("hot" → "*ot", "h*t", "ho*"). Words sharing a pattern are neighbours, so neighbours of a word are found by looking up its L patterns.
Memory layout
A hash map from pattern to the list of words, with N · L entries.
| Operation | Cost |
|---|---|
| build | O(N · L²) |
| neighbour lookup | O(L) patterns |
Run BFS from beginWord and from endWord simultaneously, always expanding the smaller frontier. The searches meet in the middle, and the number of explored words grows like b^(d/2) instead of b^d.
Memory layout
Two hash sets for the frontiers; the dictionary set doubles as the visited set.
| Operation | Cost |
|---|---|
| worst case | same O(N · L²), far fewer nodes in practice |
Run BFS from beginWord. To find the neighbours of a word, compare it with every word in the list and keep those that differ by one letter and have not been reached.
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if (find(wordList.begin(), wordList.end(), endWord) == wordList.end()) return 0;
auto differByOne = [](const string& a, const string& b) {
if (a.size() != b.size()) return false;
int diff = 0;
for (size_t i = 0; i < a.size(); i++) if (a[i] != b[i] && ++diff > 1) return false;
return diff == 1;
};
unordered_map<string, int> dist{{beginWord, 1}};
vector<string> queue{beginWord};
for (size_t head = 0; head < queue.size(); head++) {
string word = queue[head];
if (word == endWord) return dist[word];
for (const string& next : wordList) {
if (!dist.count(next) && differByOne(word, next)) {
dist[next] = dist[word] + 1;
queue.push_back(next);
}
}
}
return 0;
}public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord)) return 0;
Map<String, Integer> dist = new HashMap<>(); dist.put(beginWord, 1);
List<String> queue = new ArrayList<>(); queue.add(beginWord);
for (int head = 0; head < queue.size(); head++) {
String word = queue.get(head);
if (word.equals(endWord)) return dist.get(word);
for (String next : wordList) {
if (!dist.containsKey(next) && differByOne(word, next)) {
dist.put(next, dist.get(word) + 1);
queue.add(next);
}
}
}
return 0;
}
private boolean differByOne(String a, String b) {
if (a.length() != b.length()) return false;
int diff = 0;
for (int i = 0; i < a.length(); i++) if (a.charAt(i) != b.charAt(i) && ++diff > 1) return false;
return diff == 1;
}def ladder_length(begin_word, end_word, word_list):
if end_word not in word_list: return 0
def differ_by_one(a, b):
if len(a) != len(b): return False
diff = 0
for x, y in zip(a, b):
if x != y:
diff += 1
if diff > 1: return False
return diff == 1
dist = {begin_word: 1}
queue = [begin_word]
head = 0
while head < len(queue):
word = queue[head]; head += 1
if word == end_word: return dist[word]
for nxt in word_list:
if nxt not in dist and differ_by_one(word, nxt):
dist[nxt] = dist[word] + 1
queue.append(nxt)
return 0function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
if (!wordList.includes(endWord)) return 0;
const differByOne = (a: string, b: string): boolean => {
let diff = 0;
for (let i = 0; i < a.length; i++) if (a[i] !== b[i] && ++diff > 1) return false;
return diff === 1;
};
const dist = new Map<string, number>([[beginWord, 1]]);
const queue: string[] = [beginWord];
for (let head = 0; head < queue.length; head++) {
const word = queue[head];
if (word === endWord) return dist.get(word)!;
for (const next of wordList) {
if (!dist.has(next) && differByOne(word, next)) {
dist.set(next, dist.get(word)! + 1);
queue.push(next);
}
}
}
return 0;
}Say: BFS visits words in non-decreasing distance order, so the first time endWord is dequeued its distance is minimal.
Say: Yes: without it the same word is re-enqueued many times, and cycles make the search infinite.
Say: Try every letter substitution (26 · L candidates) or use wildcard buckets.
Store the dictionary in a hash set. For each word, replace each position with every letter a–z and keep the candidates that are in the set and unseen.
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
if (!words.count(endWord)) return 0;
vector<pair<string, int>> queue{{beginWord, 1}};
unordered_set<string> seen{beginWord};
for (size_t head = 0; head < queue.size(); head++) {
auto [word, steps] = queue[head];
if (word == endWord) return steps;
for (size_t i = 0; i < word.size(); i++) {
for (int c = 97; c < 123; c++) {
string next = word; next[i] = (char)c;
if (words.count(next) && !seen.count(next)) {
seen.insert(next);
queue.push_back({next, steps + 1});
}
}
}
}
return 0;
}public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) return 0;
List<Object[]> queue = new ArrayList<>(); queue.add(new Object[]{beginWord, 1});
Set<String> seen = new HashSet<>(); seen.add(beginWord);
for (int head = 0; head < queue.size(); head++) {
String word = (String) queue.get(head)[0]; int steps = (Integer) queue.get(head)[1];
if (word.equals(endWord)) return steps;
for (int i = 0; i < word.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
String next = word.substring(0, i) + c + word.substring(i + 1);
if (words.contains(next) && !seen.contains(next)) {
seen.add(next);
queue.add(new Object[]{next, steps + 1});
}
}
}
}
return 0;
}def ladder_length(begin_word, end_word, word_list):
words = set(word_list)
if end_word not in words: return 0
queue = [(begin_word, 1)]
seen = {begin_word}
head = 0
while head < len(queue):
word, steps = queue[head]; head += 1
if word == end_word: return steps
for i in range(len(word)):
for c in range(97, 123):
nxt = word[:i] + chr(c) + word[i + 1:]
if nxt in words and nxt not in seen:
seen.add(nxt)
queue.append((nxt, steps + 1))
return 0function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
const words = new Set(wordList);
if (!words.has(endWord)) return 0;
const queue: [string, number][] = [[beginWord, 1]];
const seen = new Set<string>([beginWord]);
for (let head = 0; head < queue.length; head++) {
const [word, steps] = queue[head];
if (word === endWord) return steps;
for (let i = 0; i < word.length; i++) {
for (let c = 97; c < 123; c++) {
const next = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
if (words.has(next) && !seen.has(next)) {
seen.add(next);
queue.push([next, steps + 1]);
}
}
}
}
return 0;
}Say: When N is large compared with 26 · L: each word costs 26 · L hash lookups instead of N comparisons.
Say: The 26 would become the alphabet size, and wildcard buckets then win because their cost does not depend on it.
Say: Group words by wildcard pattern so neighbours are found by lookup.
Precompute a map from each pattern (one letter replaced by *) to the words that match it. A word's neighbours are the other members of its L buckets; clear a bucket after using it.
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if (find(wordList.begin(), wordList.end(), endWord) == wordList.end()) return 0;
unordered_map<string, vector<string>> buckets;
vector<string> all{beginWord}; all.insert(all.end(), wordList.begin(), wordList.end());
for (const string& word : all) {
for (size_t i = 0; i < word.size(); i++) {
string pattern = word.substr(0, i) + '*' + word.substr(i + 1);
buckets[pattern].push_back(word);
}
}
vector<pair<string, int>> queue{{beginWord, 1}};
unordered_set<string> seen{beginWord};
for (size_t head = 0; head < queue.size(); head++) {
auto [word, steps] = queue[head];
if (word == endWord) return steps;
for (size_t i = 0; i < word.size(); i++) {
string pattern = word.substr(0, i) + '*' + word.substr(i + 1);
for (const string& next : buckets[pattern]) {
if (!seen.count(next)) { seen.insert(next); queue.push_back({next, steps + 1}); }
}
buckets[pattern].clear();
}
}
return 0;
}public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord)) return 0;
Map<String, List<String>> buckets = new HashMap<>();
List<String> all = new ArrayList<>(); all.add(beginWord); all.addAll(wordList);
for (String word : all) {
for (int i = 0; i < word.length(); i++) {
String pattern = word.substring(0, i) + "*" + word.substring(i + 1);
buckets.computeIfAbsent(pattern, k -> new ArrayList<>()).add(word);
}
}
List<Object[]> queue = new ArrayList<>(); queue.add(new Object[]{beginWord, 1});
Set<String> seen = new HashSet<>(); seen.add(beginWord);
for (int head = 0; head < queue.size(); head++) {
String word = (String) queue.get(head)[0]; int steps = (Integer) queue.get(head)[1];
if (word.equals(endWord)) return steps;
for (int i = 0; i < word.length(); i++) {
String pattern = word.substring(0, i) + "*" + word.substring(i + 1);
for (String next : buckets.getOrDefault(pattern, new ArrayList<>())) {
if (!seen.contains(next)) { seen.add(next); queue.add(new Object[]{next, steps + 1}); }
}
buckets.put(pattern, new ArrayList<>());
}
}
return 0;
}def ladder_length(begin_word, end_word, word_list):
if end_word not in word_list: return 0
buckets = defaultdict(list)
for word in [begin_word] + word_list:
for i in range(len(word)):
pattern = word[:i] + '*' + word[i + 1:]
buckets[pattern].append(word)
queue = [(begin_word, 1)]
seen = {begin_word}
head = 0
while head < len(queue):
word, steps = queue[head]; head += 1
if word == end_word: return steps
for i in range(len(word)):
pattern = word[:i] + '*' + word[i + 1:]
for nxt in buckets[pattern]:
if nxt not in seen:
seen.add(nxt); queue.append((nxt, steps + 1))
buckets[pattern] = []
return 0function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
if (!wordList.includes(endWord)) return 0;
const buckets = new Map<string, string[]>();
for (const word of [beginWord, ...wordList]) {
for (let i = 0; i < word.length; i++) {
const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
if (!buckets.has(pattern)) buckets.set(pattern, []);
buckets.get(pattern)!.push(word);
}
}
const queue: [string, number][] = [[beginWord, 1]];
const seen = new Set<string>([beginWord]);
for (let head = 0; head < queue.length; head++) {
const [word, steps] = queue[head];
if (word === endWord) return steps;
for (let i = 0; i < word.length; i++) {
const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
for (const next of buckets.get(pattern)!) {
if (!seen.has(next)) { seen.add(next); queue.push([next, steps + 1]); }
}
buckets.set(pattern, []);
}
}
return 0;
}Say: Everything in the bucket was enqueued when the bucket was first used, so a second visit could add nothing.
Say: No: the buckets are an index of the graph; edges are implicit between members of the same bucket.
Say: Buckets make each expansion cheap; bidirectional search makes fewer expansions. They combine well.
Search from both ends at once, always expanding the smaller frontier. Removing words from the dictionary set when they are first reached doubles as the visited check. Stop when a candidate lies in the other frontier.
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
if (!words.count(endWord)) return 0;
if (beginWord == endWord) return 1;
unordered_set<string> front{beginWord};
unordered_set<string> back{endWord};
words.erase(beginWord);
words.erase(endWord);
int steps = 1;
while (!front.empty() && !back.empty()) {
if (front.size() > back.size()) swap(front, back);
unordered_set<string> next;
for (const string& word : front) {
for (size_t i = 0; i < word.size(); i++) {
for (int c = 97; c < 123; c++) {
string cand = word; cand[i] = (char)c;
if (back.count(cand)) return steps + 1;
if (words.erase(cand)) next.insert(cand);
}
}
}
front = next;
steps++;
}
return 0;
}public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) return 0;
if (beginWord.equals(endWord)) return 1;
Set<String> front = new HashSet<>(); front.add(beginWord);
Set<String> back = new HashSet<>(); back.add(endWord);
words.remove(beginWord);
words.remove(endWord);
int steps = 1;
while (!front.isEmpty() && !back.isEmpty()) {
if (front.size() > back.size()) { Set<String> t = front; front = back; back = t; }
Set<String> next = new HashSet<>();
for (String word : front) {
for (int i = 0; i < word.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
String cand = word.substring(0, i) + c + word.substring(i + 1);
if (back.contains(cand)) return steps + 1;
if (words.remove(cand)) next.add(cand);
}
}
}
front = next;
steps++;
}
return 0;
}def ladder_length(begin_word, end_word, word_list):
words = set(word_list)
if end_word not in words: return 0
if begin_word == end_word: return 1
front = {begin_word}
back = {end_word}
words.discard(begin_word)
words.discard(end_word)
steps = 1
while front and back:
if len(front) > len(back): front, back = back, front
nxt = set()
for word in front:
for i in range(len(word)):
for c in range(97, 123):
cand = word[:i] + chr(c) + word[i + 1:]
if cand in back: return steps + 1
if cand in words:
words.discard(cand); nxt.add(cand)
front = nxt
steps += 1
return 0function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
const words = new Set(wordList);
if (!words.has(endWord)) return 0;
if (beginWord === endWord) return 1;
let front = new Set<string>([beginWord]);
let back = new Set<string>([endWord]);
words.delete(beginWord);
words.delete(endWord);
let steps = 1;
while (front.size > 0 && back.size > 0) {
if (front.size > back.size) [front, back] = [back, front];
const next = new Set<string>();
for (const word of front) {
for (let i = 0; i < word.length; i++) {
for (let c = 97; c < 123; c++) {
const cand = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
if (back.has(cand)) return steps + 1;
if (words.delete(cand)) next.add(cand);
}
}
}
front = next;
steps++;
}
return 0;
}Say: Frontier size drives the cost; always growing the smaller side keeps the total number of expansions near the minimum.
Say: steps counts the words from the start side up to the current front; the meeting candidate is one more word on the ladder.
Say: endWord missing from the list (0), beginWord equal to endWord (1), beginWord also in the list, and words of different lengths (which can never be neighbours).
Showing: BFS, scanning the whole list for neighbours — shares the player above; click any step to jump.
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if (find(wordList.begin(), wordList.end(), endWord) == wordList.end()) return 0;
auto differByOne = [](const string& a, const string& b) {
if (a.size() != b.size()) return false;
int diff = 0;
for (size_t i = 0; i < a.size(); i++) if (a[i] != b[i] && ++diff > 1) return false;
return diff == 1;
};
unordered_map<string, int> dist{{beginWord, 1}};
vector<string> queue{beginWord};
for (size_t head = 0; head < queue.size(); head++) {
string word = queue[head];
if (word == endWord) return dist[word];
for (const string& next : wordList) {
if (!dist.count(next) && differByOne(word, next)) {
dist[next] = dist[word] + 1;
queue.push_back(next);
}
}
}
return 0;
}public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord)) return 0;
Map<String, Integer> dist = new HashMap<>(); dist.put(beginWord, 1);
List<String> queue = new ArrayList<>(); queue.add(beginWord);
for (int head = 0; head < queue.size(); head++) {
String word = queue.get(head);
if (word.equals(endWord)) return dist.get(word);
for (String next : wordList) {
if (!dist.containsKey(next) && differByOne(word, next)) {
dist.put(next, dist.get(word) + 1);
queue.add(next);
}
}
}
return 0;
}
private boolean differByOne(String a, String b) {
if (a.length() != b.length()) return false;
int diff = 0;
for (int i = 0; i < a.length(); i++) if (a.charAt(i) != b.charAt(i) && ++diff > 1) return false;
return diff == 1;
}def ladder_length(begin_word, end_word, word_list):
if end_word not in word_list: return 0
def differ_by_one(a, b):
if len(a) != len(b): return False
diff = 0
for x, y in zip(a, b):
if x != y:
diff += 1
if diff > 1: return False
return diff == 1
dist = {begin_word: 1}
queue = [begin_word]
head = 0
while head < len(queue):
word = queue[head]; head += 1
if word == end_word: return dist[word]
for nxt in word_list:
if nxt not in dist and differ_by_one(word, nxt):
dist[nxt] = dist[word] + 1
queue.append(nxt)
return 0function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
if (!wordList.includes(endWord)) return 0;
const differByOne = (a: string, b: string): boolean => {
let diff = 0;
for (let i = 0; i < a.length; i++) if (a[i] !== b[i] && ++diff > 1) return false;
return diff === 1;
};
const dist = new Map<string, number>([[beginWord, 1]]);
const queue: string[] = [beginWord];
for (let head = 0; head < queue.length; head++) {
const word = queue[head];
if (word === endWord) return dist.get(word)!;
for (const next of wordList) {
if (!dist.has(next) && differByOne(word, next)) {
dist.set(next, dist.get(word)! + 1);
queue.push(next);
}
}
}
return 0;
}int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
if (!words.count(endWord)) return 0;
vector<pair<string, int>> queue{{beginWord, 1}};
unordered_set<string> seen{beginWord};
for (size_t head = 0; head < queue.size(); head++) {
auto [word, steps] = queue[head];
if (word == endWord) return steps;
for (size_t i = 0; i < word.size(); i++) {
for (int c = 97; c < 123; c++) {
string next = word; next[i] = (char)c;
if (words.count(next) && !seen.count(next)) {
seen.insert(next);
queue.push_back({next, steps + 1});
}
}
}
}
return 0;
}public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) return 0;
List<Object[]> queue = new ArrayList<>(); queue.add(new Object[]{beginWord, 1});
Set<String> seen = new HashSet<>(); seen.add(beginWord);
for (int head = 0; head < queue.size(); head++) {
String word = (String) queue.get(head)[0]; int steps = (Integer) queue.get(head)[1];
if (word.equals(endWord)) return steps;
for (int i = 0; i < word.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
String next = word.substring(0, i) + c + word.substring(i + 1);
if (words.contains(next) && !seen.contains(next)) {
seen.add(next);
queue.add(new Object[]{next, steps + 1});
}
}
}
}
return 0;
}def ladder_length(begin_word, end_word, word_list):
words = set(word_list)
if end_word not in words: return 0
queue = [(begin_word, 1)]
seen = {begin_word}
head = 0
while head < len(queue):
word, steps = queue[head]; head += 1
if word == end_word: return steps
for i in range(len(word)):
for c in range(97, 123):
nxt = word[:i] + chr(c) + word[i + 1:]
if nxt in words and nxt not in seen:
seen.add(nxt)
queue.append((nxt, steps + 1))
return 0function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
const words = new Set(wordList);
if (!words.has(endWord)) return 0;
const queue: [string, number][] = [[beginWord, 1]];
const seen = new Set<string>([beginWord]);
for (let head = 0; head < queue.length; head++) {
const [word, steps] = queue[head];
if (word === endWord) return steps;
for (let i = 0; i < word.length; i++) {
for (let c = 97; c < 123; c++) {
const next = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
if (words.has(next) && !seen.has(next)) {
seen.add(next);
queue.push([next, steps + 1]);
}
}
}
}
return 0;
}int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if (find(wordList.begin(), wordList.end(), endWord) == wordList.end()) return 0;
unordered_map<string, vector<string>> buckets;
vector<string> all{beginWord}; all.insert(all.end(), wordList.begin(), wordList.end());
for (const string& word : all) {
for (size_t i = 0; i < word.size(); i++) {
string pattern = word.substr(0, i) + '*' + word.substr(i + 1);
buckets[pattern].push_back(word);
}
}
vector<pair<string, int>> queue{{beginWord, 1}};
unordered_set<string> seen{beginWord};
for (size_t head = 0; head < queue.size(); head++) {
auto [word, steps] = queue[head];
if (word == endWord) return steps;
for (size_t i = 0; i < word.size(); i++) {
string pattern = word.substr(0, i) + '*' + word.substr(i + 1);
for (const string& next : buckets[pattern]) {
if (!seen.count(next)) { seen.insert(next); queue.push_back({next, steps + 1}); }
}
buckets[pattern].clear();
}
}
return 0;
}public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord)) return 0;
Map<String, List<String>> buckets = new HashMap<>();
List<String> all = new ArrayList<>(); all.add(beginWord); all.addAll(wordList);
for (String word : all) {
for (int i = 0; i < word.length(); i++) {
String pattern = word.substring(0, i) + "*" + word.substring(i + 1);
buckets.computeIfAbsent(pattern, k -> new ArrayList<>()).add(word);
}
}
List<Object[]> queue = new ArrayList<>(); queue.add(new Object[]{beginWord, 1});
Set<String> seen = new HashSet<>(); seen.add(beginWord);
for (int head = 0; head < queue.size(); head++) {
String word = (String) queue.get(head)[0]; int steps = (Integer) queue.get(head)[1];
if (word.equals(endWord)) return steps;
for (int i = 0; i < word.length(); i++) {
String pattern = word.substring(0, i) + "*" + word.substring(i + 1);
for (String next : buckets.getOrDefault(pattern, new ArrayList<>())) {
if (!seen.contains(next)) { seen.add(next); queue.add(new Object[]{next, steps + 1}); }
}
buckets.put(pattern, new ArrayList<>());
}
}
return 0;
}def ladder_length(begin_word, end_word, word_list):
if end_word not in word_list: return 0
buckets = defaultdict(list)
for word in [begin_word] + word_list:
for i in range(len(word)):
pattern = word[:i] + '*' + word[i + 1:]
buckets[pattern].append(word)
queue = [(begin_word, 1)]
seen = {begin_word}
head = 0
while head < len(queue):
word, steps = queue[head]; head += 1
if word == end_word: return steps
for i in range(len(word)):
pattern = word[:i] + '*' + word[i + 1:]
for nxt in buckets[pattern]:
if nxt not in seen:
seen.add(nxt); queue.append((nxt, steps + 1))
buckets[pattern] = []
return 0function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
if (!wordList.includes(endWord)) return 0;
const buckets = new Map<string, string[]>();
for (const word of [beginWord, ...wordList]) {
for (let i = 0; i < word.length; i++) {
const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
if (!buckets.has(pattern)) buckets.set(pattern, []);
buckets.get(pattern)!.push(word);
}
}
const queue: [string, number][] = [[beginWord, 1]];
const seen = new Set<string>([beginWord]);
for (let head = 0; head < queue.length; head++) {
const [word, steps] = queue[head];
if (word === endWord) return steps;
for (let i = 0; i < word.length; i++) {
const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
for (const next of buckets.get(pattern)!) {
if (!seen.has(next)) { seen.add(next); queue.push([next, steps + 1]); }
}
buckets.set(pattern, []);
}
}
return 0;
}int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
if (!words.count(endWord)) return 0;
if (beginWord == endWord) return 1;
unordered_set<string> front{beginWord};
unordered_set<string> back{endWord};
words.erase(beginWord);
words.erase(endWord);
int steps = 1;
while (!front.empty() && !back.empty()) {
if (front.size() > back.size()) swap(front, back);
unordered_set<string> next;
for (const string& word : front) {
for (size_t i = 0; i < word.size(); i++) {
for (int c = 97; c < 123; c++) {
string cand = word; cand[i] = (char)c;
if (back.count(cand)) return steps + 1;
if (words.erase(cand)) next.insert(cand);
}
}
}
front = next;
steps++;
}
return 0;
}public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) return 0;
if (beginWord.equals(endWord)) return 1;
Set<String> front = new HashSet<>(); front.add(beginWord);
Set<String> back = new HashSet<>(); back.add(endWord);
words.remove(beginWord);
words.remove(endWord);
int steps = 1;
while (!front.isEmpty() && !back.isEmpty()) {
if (front.size() > back.size()) { Set<String> t = front; front = back; back = t; }
Set<String> next = new HashSet<>();
for (String word : front) {
for (int i = 0; i < word.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
String cand = word.substring(0, i) + c + word.substring(i + 1);
if (back.contains(cand)) return steps + 1;
if (words.remove(cand)) next.add(cand);
}
}
}
front = next;
steps++;
}
return 0;
}def ladder_length(begin_word, end_word, word_list):
words = set(word_list)
if end_word not in words: return 0
if begin_word == end_word: return 1
front = {begin_word}
back = {end_word}
words.discard(begin_word)
words.discard(end_word)
steps = 1
while front and back:
if len(front) > len(back): front, back = back, front
nxt = set()
for word in front:
for i in range(len(word)):
for c in range(97, 123):
cand = word[:i] + chr(c) + word[i + 1:]
if cand in back: return steps + 1
if cand in words:
words.discard(cand); nxt.add(cand)
front = nxt
steps += 1
return 0function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
const words = new Set(wordList);
if (!words.has(endWord)) return 0;
if (beginWord === endWord) return 1;
let front = new Set<string>([beginWord]);
let back = new Set<string>([endWord]);
words.delete(beginWord);
words.delete(endWord);
let steps = 1;
while (front.size > 0 && back.size > 0) {
if (front.size > back.size) [front, back] = [back, front];
const next = new Set<string>();
for (const word of front) {
for (let i = 0; i < word.length; i++) {
for (let c = 97; c < 123; c++) {
const cand = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
if (back.has(cand)) return steps + 1;
if (words.delete(cand)) next.add(cand);
}
}
}
front = next;
steps++;
}
return 0;
}