126 · Word Ladder II — visual guide

Enumerate all shortest transformation sequences without memory explosion: Machine 1 (BFS) builds a layer graph with end-of-level visited pruning. Machine 2 (DFS) reconstructs all valid path sequences.

Execution Stage

idle

INVARIANT Dual-Machine Invariant: Visited words are pruned ONLY at the end of each entire BFS level. This allows converging paths to share the same intermediate child. Once the DAG is built, DFS reconstructs all shortest paths with zero dead ends.

Current Machine BFS

Shortest Length 5

Paths Found 0

Shortest Path Sequences 0 paths

Press Run to trace Dual-Machine Word Ladder II.

0 / 0

Speed

Java · Reference Algorithm

INTERVIEW SCRIPT

How to Present Word Ladder II to an Interviewer

1. The Memory Explosion Trap

"Attempting to carry full path lists inside the BFS queue consumes $O(N \cdot L \cdot b^d)$ space, causing Memory Limit Exceeded (MLE) on LeetCode."

2. Machine 1: BFS Layer Graph

"BFS builds a directed layer DAG (parent map Map<String, List<String>>) tracking only directed parent-to-child edges."

3. End-of-Level Visited Pruning

"Crucially, words discovered in level $k$ cannot be deleted immediately! They must remain available until the entire level finishes, so multiple parents can adopt the same child."

4. Machine 2: DFS Path Backtracking

"Once BFS terminates at the first layer containing endWord, a clean DFS backtracking recursion walks the DAG from beginWord to endWord to enumerate all optimal paths."