Shortest Word Transformation Chain
Problem
Given a beginWord, an endWord, and a list of valid intermediate words, return the number of words in the shortest chain that transforms begin into end one letter at a time. Every intermediate word must be in the dictionary. Return 0 if no chain 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).
Input
begin = "hit", end = "cog", words = [hot, dot, dog, lot, log, cog]Output
5hit → hot → dot → dog → cog (or via lot/log) is 5 words.
from 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;
}