Word Ladder
Hard BFS on implicit graph
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Transform beginWord into endWord by changing one letter at a time, where every intermediate word must be in wordList. Return the number of words in the shortest such sequence, or 0.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the shortest chain of one-letter changes from begin to end.
Why this works: words are nodes and one-letter changes are edges. The shortest path in an unweighted graph is BFS.
Example: hit → hot → dot → dog → cog
5 words✦Hints open one at a time
↗Approach
BFS level by level from beginWord. For each word, try every one-letter change; if it's endWord, return level + 1; if it's in the set, remove it and enqueue it.
</>Solution (Java)
import java.util.*;
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) return 0;
Queue<String> q = new ArrayDeque<>();
q.offer(beginWord);
int level = 1;
while (!q.isEmpty()) {
for (int i = q.size(); i > 0; i--) {
char[] w = q.poll().toCharArray();
for (int p = 0; p < w.length; p++) {
char orig = w[p];
for (char c = 'a'; c <= 'z'; c++) {
if (c == orig) continue;
w[p] = c;
String next = new String(w);
if (next.equals(endWord)) return level + 1;
if (words.remove(next)) q.offer(next); // remove = mark visited
}
w[p] = orig;
}
}
level++;
}
return 0;
}
}!Common mistake
Comparing every pair of words to build edges — O(N² · L).
- Time: O(N · L · 26), N = words, L = word length.
- Space: O(N · L).