A copy-desk service is given a begin token, a target token, and a glossary of legal words. Each rewrite may change one letter; every intermediate must sit in the glossary; the SLA is the shortest chain — number of words, not number of edits — or a hard fail if the rewrite is impossible. The intern DFS’d every unused neighbor and, at each step, scanned the whole remaining glossary for a one-letter diff. Six tokens in staging returned. Five thousand glossary entries in production were still walking when the request timed out.
Word Ladder asks for the length of the shortest transformation sequence from beginWord to endWord — the number of words in the chain — or 0 if none exists. This is an interview writeup, not a layout lecture. The graphs post owns the layout; the BFS post owns the queue. Here we only care about an implicit edge when two words differ by one letter, hop count from beginWord, and a wildcard bucket so neighbor lookup is not a dict scan. Rotting Oranges is the same hop-count BFS on a crate, seeded from every rotten cell. This walk is one source on a dictionary. Word Search walks letters on a raster; this walks whole words.
The problem
Given a String beginWord, a String endWord, and a List<String> wordList, return the number of words in the shortest sequence beginWord → … → endWord where each adjacent pair differs by exactly one letter and every word after beginWord sits in wordList. Return 0 if no such sequence exists. All words share a length. beginWord may be absent from wordList. endWord is typically required to be present.
beginWord = hit
endWord = cog
wordList = [hot, dot, dog, lot, log, cog]
→ 5
hit → hot → dot → dog → cog
beginWord = hit
endWord = cog
wordList = [hot, dot, dog, lot, log]
→ 0
beginWord = hot
endWord = dog
wordList = [hot, dog, dot]
→ 3
hot → dot → dog
beginWord = a
endWord = c
wordList = [a, b, c]
→ 2
a → cFirst row: four edits, five words. Second: cog is missing, so the target is not a legal last hop. Third: hot is already in the list; the chain still counts it once. Fourth: one letter apart, length 2.
Note: Length counts words, not edits. hit → cog in four substitutions is 5. Impossible is 0 here, not the -1 Rotting Oranges returns for leftover fresh. The prompt keeps beginWord != endWord. If endWord is not in wordList, return 0 before you search.
DFS every unused neighbor is the honest brute force
From the current word, try every unused dictionary word that differs by one letter, recurse, undo, and keep the shortest chain that lands on endWord. You do not stop at the first success; a later branch might be shorter. Correct. Exponential.
int ladderLengthDfs(String beginWord, String endWord, List<String> wordList) {
Set<String> unused = new HashSet<>(wordList);
return dfs(beginWord, endWord, unused);
}
int dfs(String cur, String endWord, Set<String> unused) {
if (cur.equals(endWord)) {
return 1;
}
int best = 0;
for (String w : new ArrayList<>(unused)) {
if (!oneLetter(cur, w)) {
continue;
}
unused.remove(w);
int len = dfs(w, endWord, unused);
unused.add(w);
if (len > 0) {
int chain = len + 1;
best = best == 0 ? chain : Math.min(best, chain);
}
}
return best;
}
boolean oneLetter(String a, String b) {
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;
}At six glossary entries this is a rounding error. At n in the thousands you paid every simple path, and at every recursive step you asked the whole remaining dict “are you one letter away?”: you scanned the glossary at every hop for a question one BFS and a wildcard bucket answers in a single walk.
One BFS on the one-letter graph
Treat each word as a vertex. An edge exists when two words differ by one letter. BFS from beginWord finds the nearest endWord. The length is that hop count, counting the words. Do not re-derive it here.
Neighbor generation is the other tax. Scanning wordList at every dequeued word is O(n) per step. Pre-bucket every glossary word by a wildcard pattern: hot sits in *ot, h*t, and ho*. From hit, the pattern h*t returns hot without walking the dict. Build the map from wordList only — beginWord may be missing, and it still generates patterns against those buckets.
Mark when you enqueue: remove the neighbor from the unused set, then offer.
beginWord = hit endWord = cog
wordList = hot, dot, dog, lot, log, cog
buckets (each word in L slots):
*ot → hot, dot, lot
h*t → hot
ho* → hot
d*t → dot
do* → dog, dot
*og → cog, dog, log
...
seed hit unused has the six glossary words
length=1 hit
patterns *it, h*t, hi* → hot mark hot
length=2 hot
→ dot, lot mark both
length=3 dot, lot
dot → dog
lot → log
length=4 dog, log
dog → cog mark cog
length=5 cog → 5Drop cog from the list and the early contains miss returns 0. There is no raster and no 4-direction table. Neighbors are other dictionary words that share a pattern. The Java is that walk. Use Deque and ArrayDeque, not java.util.Stack, not ArrayList.remove(0).
int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> unused = new HashSet<>(wordList);
if (!unused.contains(endWord)) {
return 0;
}
Map<String, List<String>> buckets = new HashMap<>();
for (String w : wordList) {
for (int i = 0; i < w.length(); i++) {
String pattern = w.substring(0, i) + '*' + w.substring(i + 1);
List<String> bucket = buckets.get(pattern);
if (bucket == null) {
bucket = new ArrayList<>();
buckets.put(pattern, bucket);
}
bucket.add(w);
}
}
Deque<String> q = new ArrayDeque<>();
q.offer(beginWord);
unused.remove(beginWord);
int length = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String cur = q.poll();
if (cur.equals(endWord)) {
return length;
}
for (int p = 0; p < cur.length(); p++) {
String pattern = cur.substring(0, p) + '*' + cur.substring(p + 1);
List<String> neigh = buckets.get(pattern);
if (neigh == null) {
continue;
}
for (String n : neigh) {
if (unused.remove(n)) {
q.offer(n);
}
}
}
}
length++;
}
return 0;
}Time is O(n L²) — n glossary words, length L: each word produces L patterns of cost O(L), and BFS offers each word at most once. Space is O(n L) for the buckets and the queue.
Note: Mark when you enqueue. unused.remove(n) before offer. Wait until poll and two parents both enqueue the same word, and that word is processed twice. Length counts words. Seed length = 1 for beginWord; increment after the wave. If endWord is missing, return 0. The unused set is the dictionary; beginWord does not have to be in it.
What interviewers usually poke next
- Bidirectional BFS. Grow a front from
beginWordand a front fromendWorduntil they meet. Fewer visited words on a bushy glossary. Follow-up, not the default board — say the single-source hop first. - The chains, not the length. All shortest sequences. BFS to record parents, then emit paths. This file stays the integer.
- Twenty-six letters instead of buckets. For each position try
a–zand probe aHashSet. Same BFS, no pattern map. They may ask which is cheaper forL = 10,n = 5000. - Word Search. Letters on a grid, 4-direction, mark-and-undo. This is whole words, one-letter neighbors, BFS for shortest. Do not walk the dictionary as a raster.
- Rotting Oranges. Multi-source hop count on a crate. This is one source. Impossible is
0here,-1there.
You are done with this problem when you can say, out loud, why DFS of every chain is correct, why BFS on the one-letter graph is the length, and why a wildcard bucket plus mark-on-enqueue is what keeps the walk linear in the glossary.