Word Ladder II
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
- Every adjacent pair of words differs by a single letter.
- Every
sifor1 <= i <= kis inwordList. Note thatbeginWorddoes not need to be inwordList. sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].
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"]]There are 2 shortest transformation sequences: hit -> hot -> dot -> dog -> cog and hit -> hot -> lot -> log -> cog.
Example 2
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]Output
[]The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
Constraints
1 <= beginWord.length <= 5endWord.length == beginWord.length1 <= wordList.length <= 500wordList[i].length == beginWord.lengthbeginWord,endWord, andwordList[i]consist of lowercase English letters.beginWord != endWord- All the words in
wordListare unique. - The sum of all shortest transformation sequences does not exceed
10^5.