Word Ladder II

Given beginWord, endWord, and a wordList, return all shortest transformation sequences from beginWord to endWord, where each step changes exactly one letter and every intermediate word is in wordList. Return each sequence as its words joined by -> (e.g. "hit->hot->...->cog"); the order of the returned sequences does not matter. Return an empty list if no sequence exists.

Hints

· Stuck? Reveal one nudge at a time.

First BFS from beginWord to record each word's distance from the start.

An edge lies on a shortest path iff it changes the distance by exactly one.

DFS backward from endWord following only those edges to enumerate all shortest ladders.

Common doubts

Storing every partial path in the BFS queue can blow up memory; distances plus a backward DFS keep only O(N·L) state and reconstruct paths one at a time.

Only step to a neighbour whose distance is one less than the current word's — those edges are exactly the ones on some shortest path.

No — the set of shortest sequences is the answer; here they're sorted for a canonical form.

Interview follow-ups

· What an interviewer asks next.

Searching from both ends and meeting in the middle shrinks the explored frontier, useful for large dictionaries.

Many independent one-letter choices at each level multiply into exponentially many shortest paths.

Fun facts

LeetCode 126 — the 'return all paths' escalation of Word Ladder.
The distance-gradient DFS is the general recipe for enumerating all shortest paths in any unweighted graph.

Asked at

AmazonFacebookGoogle

Frequently Sometimes Occasionally

Example 1

Input: beginWord = "hit", endWord = "cog", wordList = [hot,dot,dog,lot,log,cog]
Output: ["hit->hot->dot->dog->cog", "hit->hot->lot->log->cog"]
Both ladders have length 5; no shorter one exists.

Example 2

Input: beginWord = "hit", endWord = "cog", wordList = [hot,dot,dog,lot,log]
Output: []
endWord 'cog' isn't reachable.

Constraints

- 1 <= word length <= 10 - 1 <= wordList.length <= 500 - all words have the same length - all words are lowercase and distinct

Word Ladder II wants every shortest ladder, not just its length. The word graph is the same (nodes = words, edges = one-letter changes), but now you must enumerate all shortest paths between two nodes.

The efficient recipe is BFS then DFS: first BFS from beginWord to compute each word's distance from the start. Then DFS backward from endWord, only stepping to a neighbour whose distance is exactly one less — those are precisely the edges lying on some shortest path. Every root-to-end walk down this distance gradient is a distinct shortest sequence.

The brute alternative carries full paths through a level-by-level BFS, collecting every path that reaches endWord on the first level it appears. Both return the same set of sequences (here sorted for a canonical answer).

Prerequisites

Before you start

· Concepts used directly in the solution.

BFS distances. shortest distance from the start to each word.

Distance-gradient DFS. step only to a neighbour one closer to the start.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“All shortest sequences, or just one?”

All of them.

“Does the order of sequences matter?”

No — the set is what matters.

The ideal opening — say it like this

I BFS from the start to get every word's distance, then DFS back from the end, only following edges that decrease the distance by one.

Each such walk is a distinct shortest ladder; I collect them all.

Understand the problem

Worked example — begin = "hit", end = "cog", list [hot,dot,dog,lot,log,cog]

two shortest ladders:
  hit->hot->dot->dog->cog
  hit->hot->lot->log->cog

Key observations

1Aha

Shortest-path edges decrease distance by one

Those are the only edges to follow.

2Aha

BFS finds distances, DFS enumerates paths

Two phases, each doing one job.

3Aha

Backward DFS avoids longer detours

Staying on the gradient guarantees shortest sequences.

Brute force vs optimal

	BFS carrying paths	BFS distances + DFS
Idea	queue whole paths, collect those reaching end	distances, then backtrack the gradient
Memory	can be exponential in stored paths	distances + one path at a time
Result	all shortest sequences	all shortest sequences

Both return the same set of shortest ladders; the two-phase version is far lighter on memory. Full code is in the Approaches selector below.

Summary

Key takeaway

BFS from beginWord for distances, then DFS back from endWord following only edges that decrease distance by one — each such walk is a distinct shortest ladder.

BFS: dist[word] from begin
DFS from end: step to nbr with dist == dist[cur]-1; record path at begin