Word Ladder II
WHAT IT SAYS
Return ALL shortest transformation sequences from the start word to the end word.
WHAT IT'S REALLY ASKING
"Carrying whole paths inside the BFS queue is how this problem kills you — the queue holds exponentially many near-identical lists. Split the job: first a plain BFS that only MEASURES (each word's distance from the start), then a separate walk that ENUMERATES, following only edges where the distance drops by exactly one. The distances form a DAG; the answers are its paths — and no dead end is ever entered."
BFS with full paths in the queue
Exponential queue memory — shared prefixes duplicated per pathExtend Word Ladder's BFS so the queue carries entire paths instead of words; when a path reaches the end word, collect it; keep expanding until the level of the first success is exhausted.
WHERE THE WORK IS WASTED — Two compounding failures. Memory: k shortest paths sharing a long common prefix store that prefix k times over — the queue is a list of lists, and every branching doubles the copies; real dictionaries produce thousands of same-length ladders and the queue explodes before the answer arrives. Correctness pressure: Word Ladder's delete-on-enqueue is now WRONG (two different shortest paths may pass through the same word at the same level, and deletion strands the second), but removing deletion entirely readmits longer paths — so this approach forces you to invent level-scoped visited rules while ALSO hauling exponential state. Both problems trace to one decision: mixing measurement and enumeration into a single pass.
Distances define a DAG; shortest paths are its walks.
Separate the two questions the naive version tangled. Question one — how far is everything? A standard word-BFS from the start computes dist[w] for every reachable word: minimal ladder length to w. Lightweight, no paths stored, and the visited rule relaxes in exactly one way: a word may be enqueued by multiple same-level predecessors (record all of them), but never by a later level. Practically: process the frontier level by level, and delete words from the dictionary only AFTER the whole level finishes — same-level co-parents all get to register before the door closes. This is the precise correction of Word Ladder I's aggressive deletion, and understanding WHY (paths need every minimal parent; distances need only one) is the heart of the problem. Question two — which sequences realise the minimum? Here is the structural gift: orient every graph edge (u, v) in the direction where dist increases by exactly 1. The result is a DAG — layered by distance, acyclic because dist strictly increases along every kept edge — and a transformation sequence is a shortest ladder IF AND ONLY IF it is a start-to-end path in this DAG. One direction: a shortest ladder must gain distance 1 per step (any step gaining less wastes a move it can never recover). Other direction: any DAG path from start to end has length exactly dist[end], hence is minimal. The enumeration space has been PRUNED TO PERFECTION before enumeration begins: every edge in the DAG lies on some shortest path, so the DFS that walks it never enters a dead end, never backtracks out of a wrong turn — its cost is proportional to the OUTPUT, which is the best any enumeration can claim. Implementation detail that halves the work: build parents[w] (all minimal predecessors) during the BFS, then DFS BACKWARD from the end word through parents, reversing each completed chain — walking backward guarantees every step lies on a ladder that actually reaches the end, whereas walking forward from the start can still wander into words whose forward cone misses the target.
Level-batched BFS recording parents, then backward DFS
BFS O(n·L²); enumeration proportional to total output size; parents map O(V + E)BFS by whole levels: for each frontier word, generate mutations; a mutation still in the dictionary joins the next frontier and records the current word as a parent; a mutation already IN the next frontier records an additional parent. Delete the next frontier's words from the dictionary after the level completes. Stop at the level containing the end word. Then DFS from the end word through parents, emitting each root-reaching chain reversed.
Value DAG, Then Walk It
YOU'LL SEE IT AGAIN WHEN
- ALL optimal solutions are demanded, and carrying candidate solutions through the search multiplies shared prefixes exponentially.
- A cheap first pass can compute each state's optimal VALUE (distance, DP score) without storing any solution.
- Edges where the value improves by exactly the step cost form a DAG whose complete paths are precisely the optimal solutions — enumeration becomes output-bounded.