Word Ladder
Word Ladder is LeetCode 127 (Hard). Return the length of the shortest transformation sequence from beginWord to endWord, changing one letter at a time, where every intermediate word must appear in wordList. Return 0 if no such sequence exists.
The answer counts words in the sequence, not the number of letter changes. With up to 5000 words of length 10, how the neighbours are found decides whether the solution is fast or quadratic.
- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord, endWord, and wordList[i] consist of lowercase English letters.
- beginWord != endWord
- All the words in wordList are unique.
Intuition
Every edge costs one transformation, so the shortest word ladder is a BFS. The only real question is what the graph is, and the answer is that it never needs to exist:
- Don't build it. Comparing every pair of words to find those one letter apart costs O(n²·L) before the search even starts.
- Generate it on the fly. For the current word, try all 26 letters at each of its L positions and keep the candidates in the word set — O(26·L) per word, however many words there are.
Removing a word from the set as it is enqueued doubles as the visited marker, so nothing is explored twice.
This is implicit graph bfs: the nodes are words and an edge is a single-letter change, but the edges are computed on demand instead of stored. Whenever the neighbours of a state are cheap to generate from the state itself, generating beats building. Minimum Genetic Mutation is the same problem with a four-letter alphabet.
Approach
Before reading on: count what it costs to find every pair of words differing by one letter when there are 5000 words. Then ask what you could generate from a single word instead, without looking at any of the others. Aim for O(n·L·26) time.
Two ways to solve it
Use this as the default, and in an interview.
- Clarity: one queue, one set, one loop.
- Correctness: the first arrival is the shortest, with nothing to reconcile.
- Cost: explores the whole frontier up to the answer's depth.
It is short enough to write without bugs under pressure.
Reach for this when the ladder is long and the branching is wide.
- Frontier: two shallow halves instead of one deep one.
- Practice: often several times fewer words expanded.
- Cost: two sets to keep in step, and an easy off-by-one where they meet.
Same worst case, reliably faster in practice.
Plain BFS wins on being short and hard to get wrong, and the two have the same worst-case bound. The steps, code and live run below follow it; bidirectional BFS appears further down, where halving the explored frontier is worth the extra bookkeeping.
Check the end word is in the list first
If endWord is absent from wordList, no shortest transformation sequence can finish on it, so return 0 immediately. The guard costs one lookup and saves searching the entire reachable set before discovering the same thing.
Generate neighbours instead of building a graph
For the current word, replace each of its L positions with each of the 26 letters and keep the results found in the word set. Every candidate is one letter away by construction, so no comparison step is needed — at 5000 words that is what lets the solution pass.
Keep the word list in a hash set
Membership of each generated candidate must be O(1). With a list instead of a set each check is a linear scan, which quietly reintroduces the quadratic cost the generation step was meant to avoid.
Remove each word from the set as it is enqueued
Delete the word from the set the moment it enters the queue:
- On enqueue: each word is added once, by whichever predecessor reaches it first.
- On pop (too late): several words in the same layer can all add it before it is popped, and the queue fills with duplicates.
Return as soon as the end word is generated
Every edge has the same cost, so word ladder bfs reaches each word by its shortest route first. The moment endWord appears, its distance is already minimal and the search can stop rather than finishing the layer.
Count words, not changes
The distance starts at 1 for beginWord and increases by one per layer, because the problem asks for the number of words in the ladder. Starting at 0 gives an answer one too small, which is the usual wrong submission.
Word Ladder solution in Python | C++ | Java
hit off the queue. Everything reachable in 1 word(s) is expanded before anything that needs more, which is what makes the first arrival the shortest.hit yields nothing new — every match is either absent from the list or already reached by a route no longer than this one.hit with each of the 26 letters finds hot in the word set. Each is removed from the set as it is queued, so no other word can add it again.hit yields nothing new — every match is either absent from the list or already reached by a route no longer than this one.hot off the queue. Everything reachable in 2 word(s) is expanded before anything that needs more, which is what makes the first arrival the shortest.hot with each of the 26 letters finds dot in the word set. Each is removed from the set as it is queued, so no other word can add it again.hot yields nothing new — every match is either absent from the list or already reached by a route no longer than this one.hot yields nothing new — every match is either absent from the list or already reached by a route no longer than this one.dot off the queue. Everything reachable in 3 word(s) is expanded before anything that needs more, which is what makes the first arrival the shortest.dot yields nothing new — every match is either absent from the list or already reached by a route no longer than this one.dot yields nothing new — every match is either absent from the list or already reached by a route no longer than this one.dot with each of the 26 letters finds dog in the word set. Each is removed from the set as it is queued, so no other word can add it again.dog off the queue. Everything reachable in 4 word(s) is expanded before anything that needs more, which is what makes the first arrival the shortest.dog with each of the 26 letters finds cog in the word set. Each is removed from the set as it is queued, so no other word can add it again.hit and cog — not the number of letter changes, which is one fewer. Starting the count at 0 instead of 1 is the usual wrong submission.Bidirectional BFS
Grow a frontier from each end and stop when they touch. Each round expands whichever side is currently smaller, which keeps both frontiers shallow; the moment a generated word appears in the opposite frontier, the two halves join and their depths add up to the answer.
Common pitfalls
Comparing every pair of words to build edges
for a in words:
for b in words:
if differs_by_one(a, b): adj[a].append(b)for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':That's O(N²·L) in the word count. Generating the 26·L neighbours of a word and testing set membership is O(26·L) per word, independent of how many words exist.
Not removing words when enqueuing
if cand in words:
q.append((cand, d + 1))if cand in words:
words.discard(cand)
q.append((cand, d + 1))The same word would be reached from several predecessors and enqueued repeatedly, blowing up the queue exponentially. Since BFS finds the shortest route first, later arrivals can be discarded outright.
Skipping the endWord membership check
q = deque([(beginWord, 1)])
if endWord not in words:
return 0If the target isn't in the word list no transformation sequence exists, and the BFS would exhaust the entire reachable set before returning 0. The check is immediate and states the precondition.
Edge cases
Return 0 before any search — no legal sequence can end on a word that is not a permitted intermediate.
The queue drains without generating endWord, and the function returns 0.
That is allowed. It is the starting point, not an intermediate, so it never has to be a member.
They are simply never generated as neighbours, so they cost nothing beyond their place in the set.