Word ladder II
HardBFS for distances, then DFS to rebuild paths
Problem
Return all shortest transformation sequences from beginWord to endWord.
BFS over words that differ by one letter; the first time you reach the end is the shortest ladder.
The idea
Recording every path during BFS explodes in memory, so first BFS to compute each word's distance from the start, then DFS backwards from the end word following only steps that decrease the distance by exactly one. That reconstructs all shortest paths without storing them during the search.
The trick
- Two phases: BFS for distances, DFS for reconstruction.
- Walk backwards from the end so every path found is shortest by construction.
- Delete a level's words only after the whole level is processed.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — hit->cog Values: 0.
1BFS level by level building predecessor lists2DFS backtrack from endWord to beginWord to collect pathsInput
- array
- [0]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- begin = "hit", end = "cog", words = ["hot","dot","dog","lot","log","cog"]
- Output:
- 5
- Explanation:
- hit→hot→dot→dog→cog is 5 words long.
Example 2
- Input:
- begin = "a", end = "c", words = ["a","b","c"]
- Output:
- 2
- Explanation:
- a→c directly → length 2.
Example 3
- Input:
- begin = "hit", end = "cog", words = ["hot","dot","dog","lot","log"]
- Output:
- 0
- Explanation:
- 'cog' missing → 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.