1054. Word Ladder II — All Shortest Paths

Given beginWord, endWord, and a wordList of equal-length words, return all shortest transformation sequences from beginWord to endWord, changing one letter at a time where each intermediate word is in wordList. Each sequence is a list of words; return the list of all shortest sequences sorted in ascending order, or an empty list if none exist. The input is JSON {beginWord, endWord, wordList}.

Input: JSON {beginWord, endWord, wordList}.

Output: Nested array — all shortest sequences, sorted.

Examples

Input: {"beginWord":"hit","endWord":"cog","wordList":["hot","dot","dog","lot","log","cog"]}
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: Two shortest ladders.

Input: {"beginWord":"hit","endWord":"cog","wordList":["hot","dot","dog","lot","log"]}
Output: []
Explanation: endWord not reachable.

Input: {"beginWord":"a","endWord":"c","wordList":["a","b","c"]}
Output: [["a","c"]]
Explanation: Direct transform.

Constraints

• 1<=words<=500
• equal-length lowercase

Asked by