Word Ladder
Problem
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that: Every adjacent pair of words differs by a single letter. Every si for 1 <= i <= k is in wordList. sk == endWord Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
Words are nodes; two words are adjacent iff they differ in exactly one letter. BFS layered by mutation depth gives the shortest path; the answer is depth + 1 (counting both endpoints).
begin = "hit", end = "cog", words = [hot, dot, dog, lot, log, cog]5from collections import deque
def ladder_length(begin, end, words):
bank = set(words)
if end not in bank: return 0
seen = {begin}; q = deque([(begin, 1)])
while q:
s, d = q.popleft()
if s == end: return d
for i in range(len(s)):
for c in "abcdefghijklmnopqrstuvwxyz":
if c == s[i]: continue
t = s[:i] + c + s[i+1:]
if t in bank and t not in seen:
seen.add(t); q.append((t, d + 1))
return 0function ladderLength(begin, end, words) {
const bank = new Set(words);
if (!bank.has(end)) return 0;
const seen = new Set([begin]);
const q = [[begin, 1]];
while (q.length) {
const [s, d] = q.shift();
if (s === end) return d;
for (let i = 0; i < s.length; i++) {
for (let c = 97; c < 123; c++) {
const ch = String.fromCharCode(c);
if (ch === s[i]) continue;
const t = s.slice(0, i) + ch + s.slice(i + 1);
if (bank.has(t) && !seen.has(t)) { seen.add(t); q.push([t, d + 1]); }
}
}
}
return 0;
}int ladderLength(String begin, String end, List<String> words) {
Set<String> bank = new HashSet<>(words);
if (!bank.contains(end)) return 0;
Set<String> seen = new HashSet<>(); seen.add(begin);
Deque<Object[]> q = new ArrayDeque<>();
q.add(new Object[]{begin, 1});
while (!q.isEmpty()) {
Object[] cur = q.poll();
String s = (String) cur[0]; int d = (int) cur[1];
if (s.equals(end)) return d;
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; i++) {
char orig = arr[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == orig) continue;
arr[i] = c;
String t = new String(arr);
if (bank.contains(t) && seen.add(t)) q.add(new Object[]{t, d + 1});
}
arr[i] = orig;
}
}
return 0;
}int ladderLength(string begin, string end, vector<string>& words) {
unordered_set<string> bank(words.begin(), words.end());
if (!bank.count(end)) return 0;
unordered_set<string> seen{begin};
queue<pair<string,int>> q; q.push({begin, 1});
while (!q.empty()) {
auto [s, d] = q.front(); q.pop();
if (s == end) return d;
for (int i = 0; i < (int)s.size(); i++) {
char orig = s[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == orig) continue;
s[i] = c;
if (bank.count(s) && !seen.count(s)) { seen.insert(s); q.push({s, d + 1}); }
}
s[i] = orig;
}
}
return 0;
}Explanation
Think of each word as a spot on a map, with a road between two words whenever they differ by exactly one letter. We want the shortest chain from begin to end, and the classic tool for shortest steps on an unweighted map is BFS (breadth-first search).
BFS explores in rings: it visits every word one step away, then every word two steps away, and so on. Because it always reaches closer words first, the very first time it touches end it has used the fewest possible steps. We carry a depth d alongside each word in the queue and return it the moment we pop end.
To find a word's neighbors we try replacing each letter with every a-z. If the resulting word t is in the dictionary bank and not already seen, we mark it seen and push it with depth d + 1. The seen set keeps us from revisiting and looping forever.
Example: begin="hit", end="cog". Depth 1 is hit; depth 2 reaches hot; depth 3 reaches dot and lot; depth 4 reaches dog and log; depth 5 reaches cog. So the answer is 5 words.
If the queue empties without ever reaching end, no chain exists and we return 0.