Word Ladder II
Problem
Given two words beginWord and endWord and a word list, return all shortest transformation sequences from beginWord to endWord. Each adjacent pair differs by exactly one letter, and every intermediate word must be in the list.
beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"][["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]from collections import defaultdict, deque
def find_ladders(begin, end, word_list):
words = set(word_list)
if end not in words: return []
parents = defaultdict(set)
level = {begin}
found = False
while level and not found:
next_level = set()
for w in level: words.discard(w)
for w in level:
for i in range(len(w)):
for c in "abcdefghijklmnopqrstuvwxyz":
nw = w[:i] + c + w[i+1:]
if nw in words:
if nw == end: found = True
next_level.add(nw)
parents[nw].add(w)
level = next_level
if not found: return []
result = []
def backtrack(word, path):
if word == begin:
result.append([begin] + path[::-1])
return
for p in parents[word]:
backtrack(p, path + [word])
backtrack(end, [])
return resultfunction findLadders(begin, end, wordList) {
const words = new Set(wordList);
if (!words.has(end)) return [];
const parents = new Map();
let level = new Set([begin]);
let found = false;
while (level.size && !found) {
const next = new Set();
for (const w of level) words.delete(w);
for (const w of level) {
for (let i = 0; i < w.length; i++) {
for (let c = 97; c < 123; c++) {
const nw = w.slice(0, i) + String.fromCharCode(c) + w.slice(i + 1);
if (words.has(nw)) {
if (nw === end) found = true;
next.add(nw);
if (!parents.has(nw)) parents.set(nw, new Set());
parents.get(nw).add(w);
}
}
}
}
level = next;
}
if (!found) return [];
const result = [];
function backtrack(word, path) {
if (word === begin) { result.push([begin, ...path]); return; }
for (const p of parents.get(word) || []) backtrack(p, [word, ...path]);
}
backtrack(end, []);
return result;
}class Solution {
public List<List<String>> findLadders(String begin, String end, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
if (!words.contains(end)) return new ArrayList<>();
Map<String, Set<String>> parents = new HashMap<>();
Set<String> level = new HashSet<>(); level.add(begin);
boolean found = false;
while (!level.isEmpty() && !found) {
Set<String> next = new HashSet<>();
words.removeAll(level);
for (String w : level) {
char[] cs = w.toCharArray();
for (int i = 0; i < cs.length; i++) {
char orig = cs[i];
for (char c = 'a'; c <= 'z'; c++) {
cs[i] = c;
String nw = new String(cs);
if (words.contains(nw)) {
if (nw.equals(end)) found = true;
next.add(nw);
parents.computeIfAbsent(nw, k -> new HashSet<>()).add(w);
}
}
cs[i] = orig;
}
}
level = next;
}
List<List<String>> result = new ArrayList<>();
if (found) backtrack(end, begin, new ArrayList<>(), result, parents);
return result;
}
void backtrack(String w, String begin, List<String> path, List<List<String>> out, Map<String, Set<String>> parents) {
path.add(0, w);
if (w.equals(begin)) { out.add(new ArrayList<>(path)); }
else for (String p : parents.getOrDefault(w, new HashSet<>())) backtrack(p, begin, path, out, parents);
path.remove(0);
}
}vector<vector<string>> findLadders(string begin, string end, vector<string>& wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
if (!words.count(end)) return {};
unordered_map<string, vector<string>> parents;
unordered_set<string> level{begin};
bool found = false;
while (!level.empty() && !found) {
unordered_set<string> next;
for (auto& w : level) words.erase(w);
for (auto& w : level) {
string nw = w;
for (int i = 0; i < (int)w.size(); i++) {
char orig = nw[i];
for (char c = 'a'; c <= 'z'; c++) {
nw[i] = c;
if (words.count(nw)) {
if (nw == end) found = true;
next.insert(nw);
parents[nw].push_back(w);
}
}
nw[i] = orig;
}
}
level = next;
}
vector<vector<string>> result;
if (!found) return result;
function<void(string, vector<string>&)> bt = [&](string w, vector<string>& path) {
path.push_back(w);
if (w == begin) { vector<string> v(path.rbegin(), path.rend()); result.push_back(v); }
else for (auto& p : parents[w]) bt(p, path);
path.pop_back();
};
vector<string> path;
bt(end, path);
return result;
}Explanation
We need every shortest word chain, not just one. The plan has two phases: first a BFS that spreads outward level by level to find the shortest distance, recording which words led to which, then a backtrack that walks those links backward to rebuild all the paths.
During BFS, we process one whole level at a time. For each word w in the level, we try changing each letter to every a-z. If the new word nw is still in the dictionary, we add it to the next level and record w in parents[nw]. A word can have several parents, and that is exactly what lets us recover multiple ladders.
The key trick is removing each level's words from the set before expanding (words.discard(w)). This stops us from ever stepping backward or sideways, so every recorded parent link belongs to a genuinely shortest path.
Once end appears, we stop and run backtrack from end. It follows parents pointers back toward begin, building the path in reverse, and every time it reaches begin it saves a complete ladder.
Example: with begin="hit", end="cog", BFS finds cog has parents dog and log, which trace back through dot/lot to hot to hit, giving both ["hit","hot","dot","dog","cog"] and ["hit","hot","lot","log","cog"].