Word Ladder: BFS for the Shortest Transformation Sequence
Solve Word Ladder with BFS on an implicit word graph — intuition, a worked hit-to-cog walkthrough, JavaScript code, complexity analysis, and common mistakes.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Word Ladder looks like a word game and turns out to be a graph problem in disguise. That reframe — these strings are nodes, and "differ by one letter" is an edge — is the entire trick, and it's the same move that unlocks mazes, network hops, and puzzle solvers.
Once you see the hidden graph, the answer is the shortest path in it. And the shortest path in an unweighted graph has exactly one right tool: breadth-first search.
The subtlety is that you never build the graph. You'd drown in edges. Instead you generate a word's neighbors on the fly by trying every single-letter swap.
The problem
Given two words beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord. A valid sequence changes exactly one letter at a time, and every intermediate word must exist in wordList. Return 0 if no such sequence exists.
The count includes both endpoints. So hit → hot → dot → dog → cog is a sequence of length 5, not 4 hops.
Input: beginWord = "hit", endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5 // hit -> hot -> dot -> dog -> cog (5 words)Two constraints shape everything:
beginWorddoes not need to be inwordList, butendWordmust be — if it isn't, the answer is instantly0.- Every step changes precisely one character, so every edge has weight 1. That uniform cost is what makes BFS optimal.
The brute force baseline
The literal reading is to build the graph: compare every pair of words, add an edge when they differ by one letter, then run a shortest-path search.
function buildGraph(words) {
const graph = new Map(words.map((w) => [w, []]));
for (let i = 0; i < words.length; i++) {
for (let j = i + 1; j < words.length; j++) {
if (differByOne(words[i], words[j])) {
graph.get(words[i]).push(words[j]);
graph.get(words[j]).push(words[i]);
}
}
}
return graph;
}Comparing every pair is O(N²) pairs, and each comparison scans L characters, so constructing the edges alone costs O(N² · L) before you've searched anything. With a dictionary of tens of thousands of words that quadratic pair-check dominates and times out. Worse, most of those edges you build are never even walked. The whole graph is wasted work.
The key insight: an implicit graph plus BFS
Two ideas combine here.
First, don't materialize the graph. A word's neighbors are completely determined by its spelling: take each position, replace it with each letter a through z, and keep the candidates that exist in the dictionary. For a length-L word that's L × 26 candidates to test — independent of how many words the dictionary holds. A Set gives O(1) membership, so generating neighbors is cheap and lazy.
Second, use BFS, not DFS. Because every transformation costs exactly one step, the graph is unweighted. BFS explores the start word's neighbors first (distance 2), then their neighbors (distance 3), expanding outward layer by layer. The first time it reaches endWord, it has arrived by the fewest possible steps — that's the guarantee BFS gives on unweighted graphs, and it's why DFS (which would wander deep down one path) is the wrong choice.
The pattern name: BFS shortest path on an implicit graph.
The optimal solution
Each queue entry carries the word and the sequence length that reaches it. The critical detail is deleting a word from the set the moment you enqueue it — that marks it visited so it's never queued twice.
function ladderLength(beginWord, endWord, wordList) {
const wordSet = new Set(wordList);
if (!wordSet.has(endWord)) return 0;
let queue = [[beginWord, 1]];
while (queue.length > 0) {
const [word, length] = queue.shift();
if (word === endWord) return length;
for (let i = 0; i < word.length; i++) {
for (let c = 97; c <= 122; c++) {
const char = String.fromCharCode(c);
const nextWord = word.slice(0, i) + char + word.slice(i + 1);
if (wordSet.has(nextWord)) {
queue.push([nextWord, length + 1]);
wordSet.delete(nextWord);
}
}
}
}
return 0;
}c runs from 97 to 122 — the char codes for a to z — and String.fromCharCode(c) turns each back into a letter. word.slice(0, i) + char + word.slice(i + 1) rebuilds the word with position i swapped. When a candidate is in the set, it goes on the queue at length + 1 and is deleted so nothing revisits it. If the queue drains without ever popping endWord, no path exists and the function returns 0.
Walkthrough
Tracing beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]. cog is in the set, so BFS starts with the queue holding ["hit", 1]. Each row is one dequeue; "New morphs" are the valid neighbors found (and deleted from the set) while expanding that word.
| Pop (word, length) | New morphs enqueued | Queue after | Remaining set |
|---|---|---|---|
| (hit, 1) | hot @2 | [(hot,2)] | dot, dog, lot, log, cog |
| (hot, 2) | dot @3, lot @3 | [(dot,3), (lot,3)] | dog, log, cog |
| (dot, 3) | dog @4 | [(lot,3), (dog,4)] | log, cog |
| (lot, 3) | log @4 | [(dog,4), (log,4)] | cog |
| (dog, 4) | cog @5 | [(log,4), (cog,5)] | — |
| (log, 4) | none | [(cog,5)] | — |
| (cog, 5) | — | word === endWord | — |
When cog is dequeued its stored length is 5, so the function returns 5. Notice how BFS finished layer 3 (dot, lot) completely before touching layer 4 — that ordering is exactly what guarantees the length is minimal. Also notice dog was enqueued once (via dot) and deleted immediately, so when log later tried to reach it, it was already gone. That single deletion is what stops the queue from ballooning with duplicates.
Complexity
Let N be the number of words in the dictionary and L the length of each word.
| Approach | Time | Space | Why |
|---|---|---|---|
| Build explicit graph + BFS | O(N² · L) | O(N²) | every pair compared over L chars just to create edges |
| Implicit graph + BFS | O(N · L² · 26) | O(N · L) | N words popped, each tries L positions × 26 letters, each candidate costs O(L) to build and hash |
Every word is dequeued at most once (deletion enforces that), and expanding it generates L × 26 candidates. Building and hashing each length-L candidate is O(L), giving the L² factor. The visualizer's insight panel simplifies this to O(N × L × 26) by treating string construction as constant — a fair shorthand when word length is small. Space is O(N · L) for the set plus the queue.
Common mistakes
- Using DFS. Depth-first search finds a path, not the shortest one. On an unweighted graph only BFS's layer-by-layer order guarantees minimality.
- Deleting on dequeue instead of enqueue. If you only remove a word when you pop it, several parents can enqueue the same word first, bloating the queue and inflating work. Delete the instant you enqueue.
- Forgetting the endWord check. If
endWordisn't inwordList, no sequence can end there — return0up front. Skipping this makes BFS churn through the whole dictionary for nothing. - Off-by-one on the count. The answer counts words, including both endpoints, not the number of transformations. Start the begin word at length
1, not0. - Building neighbors by scanning the dictionary. Comparing the current word against every dictionary entry is O(N · L) per word. Generating the
26Lmutations and testing set membership is far cheaper when N is large.
Where this pattern shows up next
Implicit-graph BFS and unweighted shortest paths recur across the graph track:
- Clone Graph — traverse a graph node by node, the same BFS/queue machinery applied to copying.
- Max Area of Island — flood-fill a grid, another implicit graph where neighbors are computed, not stored.
- Find if Path Exists in Graph — pure reachability, BFS's simplest form.
- All Paths From Source to Target — when you need every path, not the shortest, and DFS becomes the right tool instead.
You can also step through Word Ladder interactively to watch the queue expand layer by layer and each valid morph light up as it's deleted from the dictionary.
FAQ
Why is BFS used for Word Ladder instead of DFS?
Because every transformation changes exactly one letter, every edge in the word graph has the same weight. On an unweighted graph, BFS visits nodes in strict order of distance from the start — all words one step away, then all two steps away, and so on. The first time it reaches endWord, it has done so in the fewest steps, so that count is guaranteed minimal. DFS dives deep down a single branch and can reach endWord by a long, non-optimal route, so it can't guarantee the shortest sequence without exploring everything.
What is the time complexity of Word Ladder?
O(N · L² · 26), where N is the number of dictionary words and L is the word length. Each word is dequeued at most once, and expanding it generates L positions × 26 letters of candidate strings, with each length-L candidate costing O(L) to construct and hash. Treating string building as constant, this is often quoted as O(N × L × 26). Space is O(N · L) for the word set and the BFS queue.
Why delete words from the set when enqueuing them?
Deleting a word marks it visited. Because BFS reaches every word by its shortest path the first time it's discovered, any later route to that same word would be equal or longer and is safe to ignore. Removing it on enqueue also prevents the queue from filling with duplicate copies of the same word queued by different parents in the same layer, which would waste time and memory. If you delete only when dequeuing, those duplicates slip in.
How do you generate a word's neighbors without building the whole graph?
For each position in the word, replace that character with each of the 26 lowercase letters and check whether the result exists in the dictionary set. A length-L word therefore has at most L × 26 candidates, and a Set answers "is this a real word?" in O(1). This produces neighbors lazily, only for words BFS actually visits, avoiding the O(N²) cost of comparing every pair of words to build explicit edges.
What happens if endWord is not in the word list?
The function returns 0 immediately. Every word in a valid sequence — including the final one — must exist in wordList. If endWord is missing, no sequence can legally end there, so there's no point running BFS at all. Checking wordSet.has(endWord) before the loop is a cheap guard that avoids scanning the entire reachable graph only to fail.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.