126. Word Ladder II
A transformation sequence morphs begin_word into end_word one letter at a time: each step changes exactly one character, and every word it produces — including end_word — must appear in the dictionary word_list (the starting word itself need not).
Where Word Ladder asks only for the shortest length, here your function receives begin_word, end_word, and word_list and returns every shortest transformation sequence, each as a list of words starting with begin_word and ending with end_word. Return an empty list if end_word is unreachable.
Your function may return the sequences in any order — the grader sorts them lexicographically before comparing. All words share the same length and use lowercase letters only.
Example 1:
Input: begin_word = "hit", end_word = "cog", word_list = ["hot", "dot", "dog", "lot", "log", "cog"]
Output: [["hit", "hot", "dot", "dog", "cog"], ["hit", "hot", "lot", "log", "cog"]]
Explanation: Both chains change one letter per step and finish in 5 words; no valid chain is shorter, and no other 5-word chain exists.
Example 2:
Input: begin_word = "hit", end_word = "cog", word_list = ["hot", "dot", "dog", "lot", "log"]
Output: []
Explanation: cog is missing from the dictionary, so no sequence can end there — the function returns an empty list and the grader prints -1.
Constraints:
- 1 ≤ word length ≤ 5
- 1 ≤ word_list.length ≤ 500
- begin_word, end_word, and every word in word_list share the same length
- All words consist of lowercase English letters only
- begin_word ≠ end_word
- The total number of shortest sequences is small enough to enumerate
Hints:
Finding one shortest chain is BFS. To recover all of them, you need to remember, for each word, every predecessor that reached it on a shortest path — not just one.
Process the BFS level by level. A word may have several parents in the previous level, but a word must never take a parent from its own level or later — remove each level from the candidate pool only after the whole level is generated.
Once BFS has built the parent lists (a DAG of shortest paths), walk backwards from end_word with DFS/backtracking, branching over every parent, and reverse each completed path.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: begin_word = "hit", end_word = "cog", word_list = ["hot", "dot", "dog", "lot", "log", "cog"]
Expected output: [["hit", "hot", "dot", "dog", "cog"], ["hit", "hot", "lot", "log", "cog"]]