DSA interview question

Word Ladder II (All Shortest Transformation Sequences)

Hard · Data structures · Topics: graph, bfs, backtracking

The problem

The word game now wants to show every shortest ladder, not just its length. Finding all shortest paths has two phases. First, BFS from the begin word records each word's distance, and it can stop at the end word's level. Then a backtracking DFS from the end word walks back only to words exactly one step closer to the start, which rebuilds every shortest sequence without ever exploring a longer path.

Example: hit → cog with [hot, dot, dog, lot, log, cog] → [hit,hot,dot,dog,cog] and [hit,hot,lot,log,cog].

Function signature

vector<vector<string>> findLadders(const string& beginWord, const string& endWord, const vector<string>& wordList);
// every shortest sequence, sorted lexicographically for display

Test cases

Input `(begin, end, dictionary)`	Output (sorted)	Explanation
`(hit, cog, [hot,dot,dog,lot,log,cog])`	`[hit,hot,dot,dog,cog] [hit,hot,lot,log,cog]`	Two ladders of length 5
`(hit, cog, [hot,dot,dog,lot,log])`	(none)	cog is missing
`(a, c, [a,b,c])`	`[a,c]`
`(red, tax, [ted,tex,red,tax,tad,den,rex,pee])`	`[red,rex,tex,tax] [red,ted,tad,tax] [red,ted,tex,tax]`	Three ladders of length 4

(Confirm: only shortest sequences are returned; words have equal length; any order is acceptable, and sorted order is shown.)

How interviewers phrase it

"Return all the shortest transformation sequences from beginWord to endWord" (LeetCode 126).

Clarifying questions to ask

Only the shortest sequences? (Yes.)
Output order? (Any.)
How many sequences can there be? (Potentially exponentially many, so the output size dominates.)

Follow-ups to expect

"Why not keep full paths in the BFS queue?"
"Why backtrack from the end?"
"Why can the BFS stop early?"
"Alternative?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview