Word Ladder II (LeetCode 126)
A transformation sequence is a chain beginWord -> s1 -> s2 -> ... -> sk in which each step swaps exactly one letter, every si (for 1 <= i <= k) is drawn from the dictionary wordList (though beginWord need not be), and the chain ends with sk == endWord.
Given beginWord, endWord, and wordList, return every transformation chain of the shortest possible length — each returned as its own list [beginWord, s1, s2, ..., endWord] — or an empty list if endWord can't be reached this way.
Worked Examples
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"][["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]hit -> hot -> dot -> dog -> cog and hit -> hot -> lot -> log -> cog.beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"][]⚖️Formal Constraints & Bounds
1 <= beginWord.length <= 5endWord.length == beginWord.length1 <= wordList.length <= 500wordList[i].length == beginWord.lengthbeginWord,endWord, andwordList[i]consist of lowercase English lettersbeginWord != endWordAll the words in
wordListare uniqueThe sum of all shortest transformation sequences does not exceed
105
Core Insight
Swapping a single visited set for a dict-of-sets 'parents' map, and batching the pool removal per layer instead of per word, is the entire delta between measuring shortest-path length and reconstructing every shortest path.
Real-World Scenario & Production Applications
Recovering every minimum-edit path between two strings (spell-correction / DNA-mutation chains), not merely the shortest distance between them.
Subproblems & Recurrence Decomposition4 Phases
Standard BFS only remembers 'have I seen this word?'. Word Ladder II instead maps every discovered word to the FULL set of parent words that can reach it in the fewest steps, which is what makes path reconstruction possible afterward.
parents = defaultdict(set)
next_layer[next_word].add(word)Step-by-Step Execution Trace Table
Hand-Executed Step Trace (begin = "hot", end = "dog", dict = ["hot","dog","dot"])
| Layer | Words In Layer | Neighbor Scan | parents Map After Layer | endWord Found? |
|---|---|---|---|---|
| 0 | {"hot"} | "hot" -> "dot" (1-letter mutation in word_set) | parents["dot"] = {"hot"} | No |
| 1 | {"dot"} | "dot" -> "dog" (1-letter mutation in word_set) | parents["dog"] = {"dot"} | Yes! found = True |
| — | Backtrack from "dog" | "dog" -> parent "dot" -> parent "hot" == beginWord | Path reversed: ["hot", "dot", "dog"] | Return [["hot","dot","dog"]] ✅ |
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"][["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]Hand-Executed Step Trace (begin = "hot", end = "dog", dict = ["hot","dog","dot"])
| Layer | Words In Layer | Neighbor Scan | parents Map After Layer | endWord Found? |
|---|---|---|---|---|
| 0 | {"hot"} | "hot" -> "dot" (1-letter mutation in word_set) | parents["dot"] = {"hot"} | No |
| 1 | {"dot"} | "dot" -> "dog" (1-letter mutation in word_set) | parents["dog"] = {"dot"} | Yes! found = True |
| — | Backtrack from "dog" | "dog" -> parent "dot" -> parent "hot" == beginWord | Path reversed: ["hot", "dot", "dog"] | Return [["hot","dot","dog"]] ✅ |
| 1 | if target not in reachable_states(): |
| 2 | return [] |
| 3 | layer = {start} |
| 4 | parents = defaultdict(set) |
| 5 | visited_states = {start} |
| 6 | found = False |
| 7 | while layer and not found: |
| 8 | next_layer = defaultdict(set) |
| 9 | for state in layer: |
| 10 | for neighbor in get_neighbors(state): |
| 11 | if neighbor in visited_states: |
| 12 | continue |
| 13 | next_layer[neighbor].add(state) |
| 14 | if neighbor == target: |
| 15 | found = True |
| 16 | visited_states |= set(next_layer.keys()) |
| 17 | merge next_layer into parents |
| 18 | layer = set(next_layer.keys()) |
| 19 | results = [] |
| 20 | if found: |
| 21 | backtrack_all_paths(target, start, parents, [target], results) |
| 22 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Word Ladder I asked for a single number: the length of the shortest path. Word Ladder II asks for all shortest transformation sequences. This distinction changes everything. In standard BFS, you discard visited words immediately upon enqueue to prevent redundant paths. But in Word Ladder II, two different parent words at depth might both validly connect to the same child word at depth , forming two parallel shortest paths! The solution requires a two-phase architecture: Phase 1 (BFS) discovers the shortest distance and builds a DAG(Directed Acyclic Graph) of parent-to-child connections, deleting visited words only after an entire level finishes. Phase 2 (DFS/Backtracking) traverses this compact DAG(Directed Acyclic Graph) from beginWord to endWord to materialize all optimal paths.
🏟️ The Analogy: The Surveyors and the Aerial Cartographer
Imagine mapping the shortest evacuation routes through a maze of canyon passes. In Phase 1, survey teams release colored smoke signals level by level. When smoke reaches a junction from two equally short trails simultaneously, both trails are marked on the map as optimal evacuation branches. Once the survey reaches the exit, Phase 2 begins: a cartographer sits down with the marked map and traces out every complete route from start to finish without ever getting lost in dead ends.
🔑 Why It Works
Deleting words from word_set between BFS levels (word_set -= current_level) permits parallel edges from different parents at the same depth, while completely preventing backwards cycles to earlier depths.
Per-Word Removal Instead of Per-Layer Removal (Word Ladder II): Removing a discovered word from the candidate pool the instant the first parent finds it (like ordinary BFS
visited) silently drops a second, equally-valid parent discovered later in the same layer. The removal from the candidate pool must be batched until the entire layer finishes expanding.Forgetting the Separate Backtracking DFS Pass (Word Ladder II): The layered BFS only builds a
parentsmap — it never enumerates paths itself. A completely separate backtracking DFS, walkingparentsbackward fromendWordtobeginWord, is required to actually produce the list of shortest sequences.Bi-directional search asymmetry: In bidirectional BFS, ensure forward and backward wavefront expansions connect accurately at the intersection boundary.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Implicit word graph + one-letter-at-a-time transformation + return ALL shortest transformation sequences, not just the count.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a word can only be a valid parent if it sits exactly one BFS layer earlier; batching a layer's removal from the candidate pool until the whole layer finishes preserves every tied-shortest parent instead of only the first one found.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting the DFS backtrack step entirely and trying to reconstruct paths during the BFS itself.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I run single-source BFS layer-by-layer, but instead of a visited set I build a parents map recording every word in the previous layer that reaches each new word. I only remove a whole layer from the candidate word set once it finishes expanding, so no valid parent is lost. Once endWord is found, I DFS backward through the parents map to enumerate every shortest path."
Complexity & Mathematical Proof
O(M^2 · N + P · M)
Look at the execution steps: the BFS layering phase is identical in cost to Word Ladder -- O(26 · M^2) per word across N words, giving O(M^2 · N). The backtracking DFS afterward walks the parents map once per output path; if there are P shortest paths of length up to M each, reconstruction costs O(P · M).
O(M · N + P · M) Auxiliary
Look at memory allocations: Call stack for the backtracking DFS is O(M) (max path depth). The parents map and word_set store O(M · N) words/pointers. The results list holds P paths of up to M words each, contributing O(P · M).
T(N, M, P) = N · (26 · M^2) + P · M = O(M^2 · N + P · M)
Derivation Progression
N · O(M^2) = O(M^2 · N)
Builds the parents map layer by layer, visiting each word at most once.
P paths × O(M) per path
Walks the parents map backward from endWord to beginWord once per distinct shortest path.
O(M^2 · N) + O(P · M) = O(M^2 · N + P · M)
BFS layering and path emission are two separate sequential phases.
Variable Definitions
Total number of words in the word dictionary
Length of each individual word
Number of distinct shortest transformation sequences found
Memory Architecture & Bounds
O(M) Backtracking DFS recursion depth
O(M · N) parents map and word_set
O(P · M) All P shortest paths of length up to M
Boundary Best / Worst Cases
if endWord is 1 step away with a single path.
for typical dictionaries with a small number of tied shortest paths.
with many tied-shortest paths (P can be exponential in pathological dictionaries).
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "find all the shortest transformation sequences". Multi-path reconstruction: BFS finds the minimum distance layer and constructs a DAG(Directed Acyclic Graph) of parent pointers; a backtracking DFS then traces all paths from endWord back to beginWord.
Word length , list .
Removing words from the available set too early prevents discovering alternative shortest paths that converge on the same word at the same depth.
Word Ladder II (LeetCode 126)
A transformation sequence is a chain beginWord -> s1 -> s2 -> ... -> sk in which each step swaps exactly one letter, every si (for 1 <= i <= k) is drawn from the dictionary wordList (though beginWord need not be), and the chain ends with sk == endWord.
Given beginWord, endWord, and wordList, return every transformation chain of the shortest possible length — each returned as its own list [beginWord, s1, s2, ..., endWord] — or an empty list if endWord can't be reached this way.
Worked Examples
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"][["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]hit -> hot -> dot -> dog -> cog and hit -> hot -> lot -> log -> cog.beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"][]⚖️Formal Constraints & Bounds
1 <= beginWord.length <= 5endWord.length == beginWord.length1 <= wordList.length <= 500wordList[i].length == beginWord.lengthbeginWord,endWord, andwordList[i]consist of lowercase English lettersbeginWord != endWordAll the words in
wordListare uniqueThe sum of all shortest transformation sequences does not exceed
105
Core Insight
Swapping a single visited set for a dict-of-sets 'parents' map, and batching the pool removal per layer instead of per word, is the entire delta between measuring shortest-path length and reconstructing every shortest path.
Real-World Scenario & Production Applications
Recovering every minimum-edit path between two strings (spell-correction / DNA-mutation chains), not merely the shortest distance between them.
Subproblems & Recurrence Decomposition4 Phases
Standard BFS only remembers 'have I seen this word?'. Word Ladder II instead maps every discovered word to the FULL set of parent words that can reach it in the fewest steps, which is what makes path reconstruction possible afterward.
parents = defaultdict(set)
next_layer[next_word].add(word)Step-by-Step Execution Trace Table
Hand-Executed Step Trace (begin = "hot", end = "dog", dict = ["hot","dog","dot"])
| Layer | Words In Layer | Neighbor Scan | parents Map After Layer | endWord Found? |
|---|---|---|---|---|
| 0 | {"hot"} | "hot" -> "dot" (1-letter mutation in word_set) | parents["dot"] = {"hot"} | No |
| 1 | {"dot"} | "dot" -> "dog" (1-letter mutation in word_set) | parents["dog"] = {"dot"} | Yes! found = True |
| — | Backtrack from "dog" | "dog" -> parent "dot" -> parent "hot" == beginWord | Path reversed: ["hot", "dot", "dog"] | Return [["hot","dot","dog"]] ✅ |
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"][["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]Hand-Executed Step Trace (begin = "hot", end = "dog", dict = ["hot","dog","dot"])
| Layer | Words In Layer | Neighbor Scan | parents Map After Layer | endWord Found? |
|---|---|---|---|---|
| 0 | {"hot"} | "hot" -> "dot" (1-letter mutation in word_set) | parents["dot"] = {"hot"} | No |
| 1 | {"dot"} | "dot" -> "dog" (1-letter mutation in word_set) | parents["dog"] = {"dot"} | Yes! found = True |
| — | Backtrack from "dog" | "dog" -> parent "dot" -> parent "hot" == beginWord | Path reversed: ["hot", "dot", "dog"] | Return [["hot","dot","dog"]] ✅ |
| 1 | if target not in reachable_states(): |
| 2 | return [] |
| 3 | layer = {start} |
| 4 | parents = defaultdict(set) |
| 5 | visited_states = {start} |
| 6 | found = False |
| 7 | while layer and not found: |
| 8 | next_layer = defaultdict(set) |
| 9 | for state in layer: |
| 10 | for neighbor in get_neighbors(state): |
| 11 | if neighbor in visited_states: |
| 12 | continue |
| 13 | next_layer[neighbor].add(state) |
| 14 | if neighbor == target: |
| 15 | found = True |
| 16 | visited_states |= set(next_layer.keys()) |
| 17 | merge next_layer into parents |
| 18 | layer = set(next_layer.keys()) |
| 19 | results = [] |
| 20 | if found: |
| 21 | backtrack_all_paths(target, start, parents, [target], results) |
| 22 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Word Ladder I asked for a single number: the length of the shortest path. Word Ladder II asks for all shortest transformation sequences. This distinction changes everything. In standard BFS, you discard visited words immediately upon enqueue to prevent redundant paths. But in Word Ladder II, two different parent words at depth might both validly connect to the same child word at depth , forming two parallel shortest paths! The solution requires a two-phase architecture: Phase 1 (BFS) discovers the shortest distance and builds a DAG(Directed Acyclic Graph) of parent-to-child connections, deleting visited words only after an entire level finishes. Phase 2 (DFS/Backtracking) traverses this compact DAG(Directed Acyclic Graph) from beginWord to endWord to materialize all optimal paths.
🏟️ The Analogy: The Surveyors and the Aerial Cartographer
Imagine mapping the shortest evacuation routes through a maze of canyon passes. In Phase 1, survey teams release colored smoke signals level by level. When smoke reaches a junction from two equally short trails simultaneously, both trails are marked on the map as optimal evacuation branches. Once the survey reaches the exit, Phase 2 begins: a cartographer sits down with the marked map and traces out every complete route from start to finish without ever getting lost in dead ends.
🔑 Why It Works
Deleting words from word_set between BFS levels (word_set -= current_level) permits parallel edges from different parents at the same depth, while completely preventing backwards cycles to earlier depths.
Per-Word Removal Instead of Per-Layer Removal (Word Ladder II): Removing a discovered word from the candidate pool the instant the first parent finds it (like ordinary BFS
visited) silently drops a second, equally-valid parent discovered later in the same layer. The removal from the candidate pool must be batched until the entire layer finishes expanding.Forgetting the Separate Backtracking DFS Pass (Word Ladder II): The layered BFS only builds a
parentsmap — it never enumerates paths itself. A completely separate backtracking DFS, walkingparentsbackward fromendWordtobeginWord, is required to actually produce the list of shortest sequences.Bi-directional search asymmetry: In bidirectional BFS, ensure forward and backward wavefront expansions connect accurately at the intersection boundary.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Implicit word graph + one-letter-at-a-time transformation + return ALL shortest transformation sequences, not just the count.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a word can only be a valid parent if it sits exactly one BFS layer earlier; batching a layer's removal from the candidate pool until the whole layer finishes preserves every tied-shortest parent instead of only the first one found.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting the DFS backtrack step entirely and trying to reconstruct paths during the BFS itself.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I run single-source BFS layer-by-layer, but instead of a visited set I build a parents map recording every word in the previous layer that reaches each new word. I only remove a whole layer from the candidate word set once it finishes expanding, so no valid parent is lost. Once endWord is found, I DFS backward through the parents map to enumerate every shortest path."
Complexity & Mathematical Proof
O(M^2 · N + P · M)
Look at the execution steps: the BFS layering phase is identical in cost to Word Ladder -- O(26 · M^2) per word across N words, giving O(M^2 · N). The backtracking DFS afterward walks the parents map once per output path; if there are P shortest paths of length up to M each, reconstruction costs O(P · M).
O(M · N + P · M) Auxiliary
Look at memory allocations: Call stack for the backtracking DFS is O(M) (max path depth). The parents map and word_set store O(M · N) words/pointers. The results list holds P paths of up to M words each, contributing O(P · M).
T(N, M, P) = N · (26 · M^2) + P · M = O(M^2 · N + P · M)
Derivation Progression
N · O(M^2) = O(M^2 · N)
Builds the parents map layer by layer, visiting each word at most once.
P paths × O(M) per path
Walks the parents map backward from endWord to beginWord once per distinct shortest path.
O(M^2 · N) + O(P · M) = O(M^2 · N + P · M)
BFS layering and path emission are two separate sequential phases.
Variable Definitions
Total number of words in the word dictionary
Length of each individual word
Number of distinct shortest transformation sequences found
Memory Architecture & Bounds
O(M) Backtracking DFS recursion depth
O(M · N) parents map and word_set
O(P · M) All P shortest paths of length up to M
Boundary Best / Worst Cases
if endWord is 1 step away with a single path.
for typical dictionaries with a small number of tied shortest paths.
with many tied-shortest paths (P can be exponential in pathological dictionaries).
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "find all the shortest transformation sequences". Multi-path reconstruction: BFS finds the minimum distance layer and constructs a DAG(Directed Acyclic Graph) of parent pointers; a backtracking DFS then traces all paths from endWord back to beginWord.
Word length , list .
Removing words from the available set too early prevents discovering alternative shortest paths that converge on the same word at the same depth.