#23HardGraph, BFS & Backtracking· Shortest-Path DAG Enumeration

Word Ladder II

A **transformation sequence** from `beginWord` to `endWord` is a list of words `beginWord = w0, w1, ..., wk = endWord` in which consecutive words differ in exactly one letter position, and every word after `w0` belongs to the dictionary `wordList`. (`beginWord` itself does not need to be in the dictionary.) Return **all** transformation sequences of minimum length. If no sequence exists, return an empty list. To make the answer unique, return the sequences sorted in lexicographic order, comparing them word by word.

Input format

beginWord: string, endWord: string, wordList: array of strings

Output format

Array of word sequences (arrays of strings), sorted lexicographically; `[]` if none exist

Examples

Input: beginWord = "cat", endWord = "dog", wordList = ["bat", "cot", "cog", "dog", "dot", "cat"]

Output: [["cat", "cot", "cog", "dog"], ["cat", "cot", "dot", "dog"]]

Both shortest sequences take three steps; they are listed in lexicographic order (cog before dot at the third position).

Input: beginWord = "abc", endWord = "xyz", wordList = ["abd", "xbc"]

Output: []

endWord is not in the dictionary, so no sequence exists.

Input: beginWord = "a", endWord = "c", wordList = ["a", "b", "c"]

Output: [["a", "c"]]

Single-letter words differ in their only position, so a and c are adjacent.

Constraints

1 <= beginWord.length <= 5
endWord.length == beginWord.length, and every wordList[i] has the same length
1 <= wordList.length <= 500
All words consist of lowercase English letters.
beginWord != endWord, and the words in wordList are distinct.
The total number of shortest sequences is at most 10^5.

Study first

Stacks, Queues & Monotonic Sequences

#graphs
#breadth-first-search
#backtracking
#strings
#hash-table