Loading…

hardGraphsLC #127Asked very often

Word Ladder

Graphs · 8 of 34 · 12 min

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s₁ -> s₂ -> ... -> sₖ such that:

Every adjacent pair of words differs by a single letter.
Every sᵢ for 1 ≤ i ≤ k is in wordList. Note that beginWord does not need to be in wordList.
sₖ == endWord.

Given two words beginWord and endWord, and a dictionary wordList, return the **number of words** in the shortest transformation sequence from `beginWord` to `endWord`, or `0` if no such sequence exists.

In plain English

We want the shortest chain of words, each one letter apart from the previous, every link present in the dictionary, ending at endWord. The answer is the number of words in that chain. It's a shortest path on an unweighted graph where nodes are words and edges connect one-letter-apart words.

Examples

Example 1

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Note: hit → hot → dot → dog → cog is a 5-word sequence — the shortest possible.

Example 2

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Note: endWord 'cog' is not in the word list, so no valid transformation sequence exists.

Example 3

Input: beginWord = "a", endWord = "c", wordList = ["a","b","c"]
Output: 2
Note: a → c is a single edit, and 'c' is in the list, so the sequence has 2 words.

Constraints

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

Clarifying questions4First question: Do I return the number of transformations or the number of words?Explore questions

Q1.Do I return the number of transformations or the number of words?
The number of words in the sequence, including beginWord and endWord. So hit → hot → ... → cog with 4 edits is length 5. My layer counter starts at 1.
Q2.Does beginWord have to be in the word list?
No — only the intermediate words and endWord must be in the list. But if endWord isn't in the list, there's no valid sequence, so I return 0 immediately.
Q3.Is each step exactly one letter changed?
Yes, adjacent words differ in exactly one position. That makes every edge cost 1, so BFS gives the shortest sequence.
Q4.How large can the dictionary get?
Up to 5000 words of length ≤ 10. That's big enough that generating neighbours (length × 26) beats scanning the list, and bidirectional BFS is worth mentioning to cut the frontier.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Build an implicit graph where each word is a node and two words are connected when they differ by exactly one letter (and both are in the word list). The shortest transformation sequence is the shortest path on this unweighted graph → BFS. From a word, generate all single-letter changes (length × 26), keep those in the word-list hash set, and explore level by level. Return the number of words on the shortest path (BFS layer count, starting at 1 for beginWord); return 0 if endWord isn't reachable. Bidirectional BFS roughly square-roots the search space and is the standout optimization.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model word transformations as a graph and run BFS for the shortest path, handle the off-by-one (count words, not edits), and — at the hard tier — reach for bidirectional BFS to tame the branching factor.

Where candidates slip

Returning the number of edits instead of the word count, forgetting the endWord-not-in-list short-circuit, scanning the dictionary instead of generating neighbours, or marking visited on dequeue (queue blows up).

How to stand out

Lead with plain BFS and its complexity, then propose bidirectional BFS, explaining the √ speedup from meeting in the middle and the 'always expand the smaller frontier' trick.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	BFS over One-Letter Neighbours	`O(N × L² × 26)`	`O(N × L)`	Lead with this — the correct, clear baseline. Phrase it as 'words are nodes, one-letter changes are edges, shortest path is BFS'.	Read
2	Bidirectional BFS (Meet in the Middle)Optimal	`O(N × L² × 26) worst case, ~√ fewer nodes in practice`	`O(N × L)`	The hard-tier standout. Bring it up after plain BFS: search from both beginWord and endWord, always expanding the smaller frontier, and stop when they meet.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewShortest one-letter word transformationDictionary large?YesNo / simplerExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

BFS over One-Letter Neighbours

TimeO(N × L² × 26)SpaceO(N × L)

Lead with this — the correct, clear baseline. Phrase it as 'words are nodes, one-letter changes are edges, shortest path is BFS'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Model each word as a node; connect two words if they differ in exactly one letter. The shortest transformation sequence is the shortest path between beginWord and endWord.

2Hint 2Explore hint

Equal edge cost ⇒ BFS finds the shortest path. Store the word list in a hash set so 'is this a valid word?' is O(1), and short-circuit to 0 if endWord isn't in it.

3Hint 3Explore hint

From each word, generate every one-letter change (each of L positions × 26 letters), keep those in the set and unvisited, and explore layer by layer. Return the layer index (starting at 1) when you reach endWord.

A · Core idea

The deceptively word-y prompt hides a textbook shortest-path-on-an-unweighted-graph.

The graph model. Each word is a node. Two words share an edge exactly when they differ in a single position — that's one legal transformation. A 'transformation sequence' is a path in this graph, and its length (in words) is the path's node count. Because each edge is one edit and all edits cost the same, the graph is unweighted, so BFS discovers nodes in order of increasing distance. The very first time BFS dequeues endWord, it has found the shortest sequence — DFS could not promise that, since it might plunge down a long chain before finding a short one.

Why the hash set, and the early exit. Validity ('is this candidate a real dictionary word?') is checked enormously often, so the word list goes into a hash set for O(1) membership. And before any search, we check: if endWord isn't in the set, no sequence can end there, so we return 0 immediately. Skipping this short-circuit just wastes a full BFS that's guaranteed to fail.

Generating neighbours by mutation, not by scanning. For each of the word's L positions, we try all 26 letters (skipping the current one) and form the candidate string. With L ≤ 10, that's ≤ 260 candidates per word — independent of the dictionary size. The alternative, scanning all N words and Hamming-comparing each, costs O(N × L) per word and balloons to O(N²) overall on a 5000-word list. For a large dictionary, generation is decisively better; that's why we generate.

Mark visited on enqueue. The instant we accept a candidate we add it to visited and the queue. Marking on dequeue instead would let several neighbours enqueue the same word before it's processed, inflating the queue and re-expanding nodes — and worse, the word graph has cycles, so without visited tracking BFS would never terminate.

Counting words, not edits. The layer counter starts at 1 because beginWord itself is the first word of the sequence. Each completed layer is one more edit, i.e. one more word. So when endWord is dequeued at layer level, level is exactly the word count the problem asks for. Starting the counter at 0 (counting edits) is the single most common off-by-one in this problem.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

begin = "hit", end = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Interactive diagram

Word graph for example 1

level=1

Active call / nodeSupporting contextReturned stateNot active

Edges connect one-letter-apart words; BFS finds the 5-word shortest chain hit→hot→dot→dog→cog.

Final result5

C · Code with teaching comments

Reference implementation previewpublic int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> wordSet = new HashSet<>(wordList); if (!wordSet.contains(endWord)) { return 0; }Explore the full code

solution.javaJava

BFS over One-Letter Neighbours — reference

5 teaching notes

1
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
2
    Set<String> wordSet = new HashSet<>(wordList);
3
    if (!wordSet.contains(endWord)) {
4
        return 0;
5
    }
6
    Queue<String> queue = new LinkedList<>();
7
    Set<String> visited = new HashSet<>();
8
    queue.offer(beginWord);
9
    visited.add(beginWord);
10
    int level = 1; // count of words, beginWord is word #1
11
    while (!queue.isEmpty()) {
12
        int size = queue.size();
13
        for (int i = 0; i < size; i++) {
14
            String word = queue.poll();
15
            if (word.equals(endWord)) {
16
                return level;
17
            }
18
            char[] arr = word.toCharArray();
19
            for (int p = 0; p < arr.length; p++) {
20
                char original = arr[p];
21
                for (char ch = 'a'; ch <= 'z'; ch++) {
22
                    if (ch == original) {
23
                        continue;
24
                    }
25
                    arr[p] = ch;
26
                    String next = new String(arr);
27
                    if (wordSet.contains(next) && !visited.contains(next)) {
28
                        visited.add(next);
29
                        queue.offer(next);
30
                    }
31
                }
32
                arr[p] = original;
33
            }
34
        }
35
        level++;
36
    }
37
    return 0;
38
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.38 lines

D · Why it works and complexityO(N × L² × 26) timeO(N × L) spaceOpen the invariant and proofExplore the proof

Word Ladder is Minimum Genetic Mutation with a 26-letter alphabet and variable length. The transferable core is 'BFS over one-edit neighbours, validity via a hash set, count layers'. The only Word-Ladder-specific subtlety is the off-by-one: it asks for the number of words, so the counter starts at 1.

ComplexityO(N × L² × 26) time, O(N × L) space — There are up to N words; each is dequeued once and produces L × 26 candidates, and building each candidate string is O(L) → O(N × L × 26 × L) = O(N × L² × 26). The visited set and queue hold O(N) words of length L → O(N × L) space.

E · Edge cases and pitfalls7endWord not in wordList — Short-circuits to 0 before any BFS.Explore edge cases

Edge cases handled

endWord not in wordListShort-circuits to 0 before any BFS.
begin one edit from end, end in listLayer 1 dequeues begin, layer 2 dequeues end → returns 2.
disconnected end (no path)BFS drains the reachable component without reaching end → returns 0.

Pitfalls

Returning the edit count instead of the word count — start the layer counter at 1.
Skipping the 'endWord not in set' check and running a doomed full BFS.
Scanning the dictionary per word (O(N²)) instead of generating L×26 neighbours.
Marking visited on dequeue — the same word gets enqueued by multiple neighbours.

03.2

Approach 2 of 2 · Optimal

Bidirectional BFS (Meet in the Middle)

TimeO(N × L² × 26) worst case, ~√ fewer nodes in practiceSpaceO(N × L)

The hard-tier standout. Bring it up after plain BFS: search from both beginWord and endWord, always expanding the smaller frontier, and stop when they meet.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

BFS from one side explores roughly b^d nodes, where b is the branching factor and d the distance. What if you searched from both ends simultaneously?

2Hint 2Explore hint

Maintain two frontiers (sets), one growing from beginWord and one from endWord. Each round, expand the smaller one and check whether any new word lands in the other frontier.

3Hint 3Explore hint

When a generated word is in the opposite frontier, the two searches have met — the answer is the levels expanded so far plus one for the connecting edge.

A · Core idea

Single-source BFS pays for the branching factor compounding over the whole distance. Bidirectional BFS attacks that exponent directly.

Why meeting in the middle helps. If each step branches into roughly b options and the answer is at distance d, a one-directional BFS touches on the order of b^d nodes. Run two BFS frontiers — one forward from beginWord, one backward from endWord — and each only needs to reach depth d/2 before they collide. That's about 2·b^(d/2) nodes, the square root of the original. For a large branching factor (26 letters per position!) and a long ladder, that's an order-of-magnitude fewer words explored.

Always expand the smaller frontier. The frontiers grow at different rates; expanding the smaller one each round keeps the total work balanced and maximizes the speedup. We implement this by swapping the two sets whenever the 'begin' frontier grows larger than the 'end' frontier, so the loop body always operates on the smaller one. This is the single most important implementation detail — without it, one runaway frontier erodes the advantage.

Detecting the meeting. For each word in the current (smaller) frontier we generate its one-letter neighbours. If a neighbour is already in the opposite frontier, the forward and backward paths have joined — we return the number of levels expanded so far plus one for that connecting edge. Otherwise, if the neighbour is a valid, unvisited dictionary word, it joins the next frontier. A shared visited set keeps the two searches from re-exploring each other's territory.

Same correctness, fewer nodes. Because both halves are BFS, each explores by increasing distance, so the first meeting corresponds to a shortest path. The endWord-not-in-list short-circuit still applies up front. The trade-off is a bit more code and care around the level bookkeeping, in exchange for searching a fraction of the graph — exactly the kind of optimization a hard-tagged problem is probing for.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

begin = "hit", end = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Interactive diagram

Picking the right approach

level=1

Active call / nodeSupporting contextReturned stateNot active

Plain BFS solves it; bidirectional BFS is the hard-tier optimization for large dictionaries.

Final result5

C · Code with teaching comments

solution.javaJava

Bidirectional BFS (Meet in the Middle) — optimal

5 teaching notes

1
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
2
    Set<String> wordSet = new HashSet<>(wordList);
3
    if (!wordSet.contains(endWord)) {
4
        return 0;
5
    }
6
    Set<String> beginSet = new HashSet<>();
7
    Set<String> endSet = new HashSet<>();
8
    Set<String> visited = new HashSet<>();
9
    beginSet.add(beginWord);
10
    endSet.add(endWord);
11
    visited.add(beginWord);
12
    visited.add(endWord);
13
    int level = 1;
14
    while (!beginSet.isEmpty() && !endSet.isEmpty()) {
15
        if (beginSet.size() > endSet.size()) { // always expand the smaller
16
            Set<String> tmp = beginSet;
17
            beginSet = endSet;
18
            endSet = tmp;
19
        }
20
        Set<String> nextSet = new HashSet<>();
21
        for (String word : beginSet) {
22
            char[] arr = word.toCharArray();
23
            for (int p = 0; p < arr.length; p++) {
24
                char original = arr[p];
25
                for (char ch = 'a'; ch <= 'z'; ch++) {
26
                    if (ch == original) {
27
                        continue;
28
                    }
29
                    arr[p] = ch;
30
                    String next = new String(arr);
31
                    if (endSet.contains(next)) { // frontiers met
32
                        return level + 1;
33
                    }
34
                    if (wordSet.contains(next) && !visited.contains(next)) {
35
                        visited.add(next);
36
                        nextSet.add(next);
37
                    }
38
                }
39
                arr[p] = original;
40
            }
41
        }
42
        beginSet = nextSet;
43
        level++;
44
    }
45
    return 0;
46
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.46 lines

D · Why it works and complexityO(N × L² × 26) worst case, ~√ fewer nodes in practice timeO(N × L) spaceOpen the invariant and proofExplore the proof

Bidirectional search is the go-to optimization whenever you have a single source, a single target, and a large branching factor. The mental model — 'two expanding wavefronts that collide halfway' — and the discipline of always expanding the smaller frontier are what turn a correct BFS into a fast one.

ComplexityO(N × L² × 26) worst case, ~√ fewer nodes in practice time, O(N × L) space — Two searches of depth ~d/2 explore about 2·b^(d/2) nodes instead of one search's b^d — a square-root reduction in the typical case. Worst-case asymptotics match plain BFS, but the constant-factor and frontier size shrink dramatically. Space is still O(N × L) for the visited set and frontiers.

E · Edge cases and pitfalls7begin adjacent to end — First expansion of begin finds end in the opposite frontier → returns 2.Explore edge cases

Edge cases handled

begin adjacent to endFirst expansion of begin finds end in the opposite frontier → returns 2.
no path existsOne frontier becomes empty → loop ends → returns 0.
highly branching dictionaryBidirectional explores far fewer words than single-source BFS — the intended win.

Pitfalls

Forgetting to always expand the smaller frontier — loses most of the speedup.
Returning level instead of level + 1 at the meeting point — off by one.
Not sharing a visited set between directions — re-exploration and possible double counting.
Checking endSet membership after the visited filter instead of before — can miss the meeting.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> wordSet = new HashSet<>(wordList); if (!wordSet.contains(endWord)) { return 0; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord)) {
        return 0;
    }
    Set<String> beginSet = new HashSet<>();
    Set<String> endSet = new HashSet<>();
    Set<String> visited = new HashSet<>();
    beginSet.add(beginWord);
    endSet.add(endWord);
    visited.add(beginWord);
    visited.add(endWord);
    int level = 1;
    while (!beginSet.isEmpty() && !endSet.isEmpty()) {
        if (beginSet.size() > endSet.size()) { // always expand the smaller
            Set<String> tmp = beginSet;
            beginSet = endSet;
            endSet = tmp;
        }
        Set<String> nextSet = new HashSet<>();
        for (String word : beginSet) {
            char[] arr = word.toCharArray();
            for (int p = 0; p < arr.length; p++) {
                char original = arr[p];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (ch == original) {
                        continue;
                    }
                    arr[p] = ch;
                    String next = new String(arr);
                    if (endSet.contains(next)) { // frontiers met
                        return level + 1;
                    }
                    if (wordSet.contains(next) && !visited.contains(next)) {
                        visited.add(next);
                        nextSet.add(next);
                    }
                }
                arr[p] = original;
            }
        }
        beginSet = nextSet;
        level++;
    }
    return 0;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Counting edits instead of words

The problem asks for the number of words in the sequence, including beginWord. If the layer counter starts at 0 it counts edges (edits), returning one less than required.

Explore the code comparison

Don't write this

level = 0          # counts edits, not words
while queue:
    for _ in range(len(queue)):
        word = queue.popleft()
        if word == endWord:
            return level   # off by one
    level += 1

Write this instead

level = 1          # beginWord is word #1
while queue:
    for _ in range(len(queue)):
        word = queue.popleft()
        if word == endWord:
            return level
    level += 1

Skipping the endWord-in-list check

If endWord isn't in the dictionary, no sequence can end there. Without the early return, you run a full BFS that's guaranteed to fail, and you must still return 0 — wasted work and an easy place to mishandle the result.

Explore the code comparison

Don't write this

Set<String> wordSet = new HashSet<>(wordList);
// no check — run BFS regardless
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);

Write this instead

Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) {
    return 0;   // no sequence can end at a non-dictionary word
}
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);

Scanning the dictionary instead of generating neighbours

Comparing the current word against all N dictionary words is O(N·L) per word, so O(N²·L) overall — quadratic in a 5000-word list. Generating L×26 mutations is independent of dictionary size.

Explore the code comparison

Don't write this

for candidate in wordList:          # O(N) per word → O(N^2)
    if hamming(word, candidate) == 1 and candidate not in visited:
        visited.add(candidate)
        queue.append(candidate)

Write this instead

for p in range(len(word)):          # O(L*26), size-independent
    for c in "abcdefghijklmnopqrstuvwxyz":
        nxt = word[:p] + c + word[p+1:]
        if nxt in word_set and nxt not in visited:
            visited.add(nxt)
            queue.append(nxt)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Shortest transformation sequence → BFS over one-letter neighbours; bidirectional BFS to scale

Code pattern to memorize

wordSet = set(wordList); if end not in wordSet: return 0
q = [begin]; seen = {begin}; level = 1
while q:
    for word in this layer:
        if word == end: return level
        for p, for c in 'a'..'z':
            cand = word with position p set to c
            if cand in wordSet and cand not in seen:
                seen.add(cand); q.push(cand)
    level += 1
return 0

Rules to remember

1Return the count of words on the shortest path (including begin and end), not the number of edits — so the layer counter starts at 1.
2If endWord is not in the word list, no sequence exists → return 0 up front.
3Each one-letter change is an equal-cost edge, so BFS (not DFS) gives the shortest sequence.
4Put the word list in a hash set for O(1) validity checks; mark words visited on enqueue.
5Generate neighbours by trying 26 letters at each position — this beats scanning a large dictionary.

Use this pattern when

Fewest single-character transformations between two words through a dictionary
Shortest path on an unweighted implicit graph of string states
Any 'minimum steps where each step is a small valid edit' problem
When the dictionary is large enough that bidirectional BFS pays off

Choose another pattern when

You must return ALL shortest sequences → Word Ladder II (BFS to layer, DFS to rebuild)
Edits have differing costs → weighted shortest path (Dijkstra)
The alphabet/length is unbounded → enumeration is infeasible; rethink the model

Interview takeaway

Word Ladder is the canonical 'shortest transformation' BFS. The base solution is BFS over one-letter neighbours with a hash set; the senior-level move is bidirectional BFS, which searches from both ends and meets in the middle, cutting the explored frontier from roughly b^d to 2·b^(d/2).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternShortest transformation BFS over an implicit graph of one-edit neighbours, with a hash set for O(1) validity. Bidirectional BFS meets in the middle to square-root the explored frontier. Same family as Minimum Genetic Mutation, Open the Lock, and Word Ladder II — the tell is 'fewest single-edit steps between two states through valid intermediates'.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Word Ladder II
Coming soon
Return ALL shortest sequences — BFS to build the layered parent graph, then DFS/backtrack to reconstruct every shortest path.
Minimum Genetic Mutation
The same BFS with a 4-letter alphabet and fixed length 8 — counts mutations (edits) rather than words.
Open the Lock
Coming soon
BFS over 4-digit lock states with ±1 wheel turns and blocked deadends — bidirectional BFS also applies.
Snakes and Ladders
Another unweighted shortest-path BFS, on a flattened board rather than strings.

Same pattern

←

Number of Connected Components in an Undirected Graph

Continue · Next problem

Course Schedule II

hardGraphsLC #127Asked very often

Word Ladder

LCPractice

Graphs · 8 of 34 · 12 min

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s₁ -> s₂ -> ... -> sₖ such that:

Every adjacent pair of words differs by a single letter.
Every sᵢ for 1 ≤ i ≤ k is in wordList. Note that beginWord does not need to be in wordList.
sₖ == endWord.

In plain English

Examples

Example 1

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Note: hit → hot → dot → dog → cog is a 5-word sequence — the shortest possible.

Example 2

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Note: endWord 'cog' is not in the word list, so no valid transformation sequence exists.

Example 3

Input: beginWord = "a", endWord = "c", wordList = ["a","b","c"]
Output: 2
Note: a → c is a single edit, and 'c' is in the list, so the sequence has 2 words.

Constraints

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

Clarifying questions4First question: Do I return the number of transformations or the number of words?Explore questions

Q1.Do I return the number of transformations or the number of words?
The number of words in the sequence, including beginWord and endWord. So hit → hot → ... → cog with 4 edits is length 5. My layer counter starts at 1.
Q2.Does beginWord have to be in the word list?
No — only the intermediate words and endWord must be in the list. But if endWord isn't in the list, there's no valid sequence, so I return 0 immediately.
Q3.Is each step exactly one letter changed?
Yes, adjacent words differ in exactly one position. That makes every edge cost 1, so BFS gives the shortest sequence.
Q4.How large can the dictionary get?
Up to 5000 words of length ≤ 10. That's big enough that generating neighbours (length × 26) beats scanning the list, and bidirectional BFS is worth mentioning to cut the frontier.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

How to stand out

Lead with plain BFS and its complexity, then propose bidirectional BFS, explaining the √ speedup from meeting in the middle and the 'always expand the smaller frontier' trick.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	BFS over One-Letter Neighbours	`O(N × L² × 26)`	`O(N × L)`	Lead with this — the correct, clear baseline. Phrase it as 'words are nodes, one-letter changes are edges, shortest path is BFS'.	Read
2	Bidirectional BFS (Meet in the Middle)Optimal	`O(N × L² × 26) worst case, ~√ fewer nodes in practice`	`O(N × L)`	The hard-tier standout. Bring it up after plain BFS: search from both beginWord and endWord, always expanding the smaller frontier, and stop when they meet.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

BFS over One-Letter Neighbours

TimeO(N × L² × 26)SpaceO(N × L)

Lead with this — the correct, clear baseline. Phrase it as 'words are nodes, one-letter changes are edges, shortest path is BFS'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Model each word as a node; connect two words if they differ in exactly one letter. The shortest transformation sequence is the shortest path between beginWord and endWord.

2Hint 2Explore hint

Equal edge cost ⇒ BFS finds the shortest path. Store the word list in a hash set so 'is this a valid word?' is O(1), and short-circuit to 0 if endWord isn't in it.

3Hint 3Explore hint

A · Core idea

The deceptively word-y prompt hides a textbook shortest-path-on-an-unweighted-graph.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

begin = "hit", end = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Interactive diagram

Word graph for example 1

level=1

Active call / nodeSupporting contextReturned stateNot active

Edges connect one-letter-apart words; BFS finds the 5-word shortest chain hit→hot→dot→dog→cog.

Final result5

C · Code with teaching comments

solution.javaJava

BFS over One-Letter Neighbours — reference

5 teaching notes

1
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
2
    Set<String> wordSet = new HashSet<>(wordList);
3
    if (!wordSet.contains(endWord)) {
4
        return 0;
5
    }
6
    Queue<String> queue = new LinkedList<>();
7
    Set<String> visited = new HashSet<>();
8
    queue.offer(beginWord);
9
    visited.add(beginWord);
10
    int level = 1; // count of words, beginWord is word #1
11
    while (!queue.isEmpty()) {
12
        int size = queue.size();
13
        for (int i = 0; i < size; i++) {
14
            String word = queue.poll();
15
            if (word.equals(endWord)) {
16
                return level;
17
            }
18
            char[] arr = word.toCharArray();
19
            for (int p = 0; p < arr.length; p++) {
20
                char original = arr[p];
21
                for (char ch = 'a'; ch <= 'z'; ch++) {
22
                    if (ch == original) {
23
                        continue;
24
                    }
25
                    arr[p] = ch;
26
                    String next = new String(arr);
27
                    if (wordSet.contains(next) && !visited.contains(next)) {
28
                        visited.add(next);
29
                        queue.offer(next);
30
                    }
31
                }
32
                arr[p] = original;
33
            }
34
        }
35
        level++;
36
    }
37
    return 0;
38
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.38 lines

D · Why it works and complexityO(N × L² × 26) timeO(N × L) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7endWord not in wordList — Short-circuits to 0 before any BFS.Explore edge cases

Edge cases handled

endWord not in wordListShort-circuits to 0 before any BFS.
begin one edit from end, end in listLayer 1 dequeues begin, layer 2 dequeues end → returns 2.
disconnected end (no path)BFS drains the reachable component without reaching end → returns 0.

Pitfalls

Returning the edit count instead of the word count — start the layer counter at 1.
Skipping the 'endWord not in set' check and running a doomed full BFS.
Scanning the dictionary per word (O(N²)) instead of generating L×26 neighbours.
Marking visited on dequeue — the same word gets enqueued by multiple neighbours.

03.2

Approach 2 of 2 · Optimal

Bidirectional BFS (Meet in the Middle)

TimeO(N × L² × 26) worst case, ~√ fewer nodes in practiceSpaceO(N × L)

The hard-tier standout. Bring it up after plain BFS: search from both beginWord and endWord, always expanding the smaller frontier, and stop when they meet.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

BFS from one side explores roughly b^d nodes, where b is the branching factor and d the distance. What if you searched from both ends simultaneously?

2Hint 2Explore hint

Maintain two frontiers (sets), one growing from beginWord and one from endWord. Each round, expand the smaller one and check whether any new word lands in the other frontier.

3Hint 3Explore hint

When a generated word is in the opposite frontier, the two searches have met — the answer is the levels expanded so far plus one for the connecting edge.

A · Core idea

Single-source BFS pays for the branching factor compounding over the whole distance. Bidirectional BFS attacks that exponent directly.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

begin = "hit", end = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Interactive diagram

Picking the right approach

level=1

Active call / nodeSupporting contextReturned stateNot active

Plain BFS solves it; bidirectional BFS is the hard-tier optimization for large dictionaries.

Final result5

C · Code with teaching comments

solution.javaJava

Bidirectional BFS (Meet in the Middle) — optimal

5 teaching notes

1
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
2
    Set<String> wordSet = new HashSet<>(wordList);
3
    if (!wordSet.contains(endWord)) {
4
        return 0;
5
    }
6
    Set<String> beginSet = new HashSet<>();
7
    Set<String> endSet = new HashSet<>();
8
    Set<String> visited = new HashSet<>();
9
    beginSet.add(beginWord);
10
    endSet.add(endWord);
11
    visited.add(beginWord);
12
    visited.add(endWord);
13
    int level = 1;
14
    while (!beginSet.isEmpty() && !endSet.isEmpty()) {
15
        if (beginSet.size() > endSet.size()) { // always expand the smaller
16
            Set<String> tmp = beginSet;
17
            beginSet = endSet;
18
            endSet = tmp;
19
        }
20
        Set<String> nextSet = new HashSet<>();
21
        for (String word : beginSet) {
22
            char[] arr = word.toCharArray();
23
            for (int p = 0; p < arr.length; p++) {
24
                char original = arr[p];
25
                for (char ch = 'a'; ch <= 'z'; ch++) {
26
                    if (ch == original) {
27
                        continue;
28
                    }
29
                    arr[p] = ch;
30
                    String next = new String(arr);
31
                    if (endSet.contains(next)) { // frontiers met
32
                        return level + 1;
33
                    }
34
                    if (wordSet.contains(next) && !visited.contains(next)) {
35
                        visited.add(next);
36
                        nextSet.add(next);
37
                    }
38
                }
39
                arr[p] = original;
40
            }
41
        }
42
        beginSet = nextSet;
43
        level++;
44
    }
45
    return 0;
46
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.46 lines

D · Why it works and complexityO(N × L² × 26) worst case, ~√ fewer nodes in practice timeO(N × L) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7begin adjacent to end — First expansion of begin finds end in the opposite frontier → returns 2.Explore edge cases

Edge cases handled

begin adjacent to endFirst expansion of begin finds end in the opposite frontier → returns 2.
no path existsOne frontier becomes empty → loop ends → returns 0.
highly branching dictionaryBidirectional explores far fewer words than single-source BFS — the intended win.

Pitfalls

Forgetting to always expand the smaller frontier — loses most of the speedup.
Returning level instead of level + 1 at the meeting point — off by one.
Not sharing a visited set between directions — re-exploration and possible double counting.
Checking endSet membership after the visited filter instead of before — can miss the meeting.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Counting edits instead of words

The problem asks for the number of words in the sequence, including beginWord. If the layer counter starts at 0 it counts edges (edits), returning one less than required.

Explore the code comparison

Don't write this

level = 0          # counts edits, not words
while queue:
    for _ in range(len(queue)):
        word = queue.popleft()
        if word == endWord:
            return level   # off by one
    level += 1

Write this instead

level = 1          # beginWord is word #1
while queue:
    for _ in range(len(queue)):
        word = queue.popleft()
        if word == endWord:
            return level
    level += 1

Skipping the endWord-in-list check

Explore the code comparison

Don't write this

Set<String> wordSet = new HashSet<>(wordList);
// no check — run BFS regardless
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);

Write this instead

Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) {
    return 0;   // no sequence can end at a non-dictionary word
}
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);

Scanning the dictionary instead of generating neighbours

Comparing the current word against all N dictionary words is O(N·L) per word, so O(N²·L) overall — quadratic in a 5000-word list. Generating L×26 mutations is independent of dictionary size.

Explore the code comparison

Don't write this

for candidate in wordList:          # O(N) per word → O(N^2)
    if hamming(word, candidate) == 1 and candidate not in visited:
        visited.add(candidate)
        queue.append(candidate)

Write this instead

for p in range(len(word)):          # O(L*26), size-independent
    for c in "abcdefghijklmnopqrstuvwxyz":
        nxt = word[:p] + c + word[p+1:]
        if nxt in word_set and nxt not in visited:
            visited.add(nxt)
            queue.append(nxt)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Shortest transformation sequence → BFS over one-letter neighbours; bidirectional BFS to scale

Code pattern to memorize

wordSet = set(wordList); if end not in wordSet: return 0
q = [begin]; seen = {begin}; level = 1
while q:
    for word in this layer:
        if word == end: return level
        for p, for c in 'a'..'z':
            cand = word with position p set to c
            if cand in wordSet and cand not in seen:
                seen.add(cand); q.push(cand)
    level += 1
return 0

Rules to remember

1Return the count of words on the shortest path (including begin and end), not the number of edits — so the layer counter starts at 1.
2If endWord is not in the word list, no sequence exists → return 0 up front.
3Each one-letter change is an equal-cost edge, so BFS (not DFS) gives the shortest sequence.
4Put the word list in a hash set for O(1) validity checks; mark words visited on enqueue.
5Generate neighbours by trying 26 letters at each position — this beats scanning a large dictionary.

Use this pattern when

Fewest single-character transformations between two words through a dictionary
Shortest path on an unweighted implicit graph of string states
Any 'minimum steps where each step is a small valid edit' problem
When the dictionary is large enough that bidirectional BFS pays off

Choose another pattern when

You must return ALL shortest sequences → Word Ladder II (BFS to layer, DFS to rebuild)
Edits have differing costs → weighted shortest path (Dijkstra)
The alphabet/length is unbounded → enumeration is infeasible; rethink the model

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Word Ladder II
Coming soon
Return ALL shortest sequences — BFS to build the layered parent graph, then DFS/backtrack to reconstruct every shortest path.
Minimum Genetic Mutation
The same BFS with a 4-letter alphabet and fixed length 8 — counts mutations (edits) rather than words.
Open the Lock
Coming soon
BFS over 4-digit lock states with ±1 wheel turns and blocked deadends — bidirectional BFS also applies.
Snakes and Ladders
Another unweighted shortest-path BFS, on a flattened board rather than strings.

Same pattern

←

Number of Connected Components in an Undirected Graph

Continue · Next problem

Course Schedule II