In a word puzzle you change one letter at a time to turn one word into another.
A transformation sequence goes from beginWord to endWord using the allowed words in wordList. It looks like beginWord -> s1 -> s2 -> ... -> sk, and it must follow these rules:
- Two neighbouring words in the sequence differ in exactly one letter.
- Every word after
beginWord must be in wordList. The word beginWord itself does not need to be in the list.
- The last word
sk must be endWord.
Your task is to find every shortest transformation sequence that starts at beginWord and ends at endWord. Give each sequence as a list of words. If there is no sequence, return an empty list.
You can return the sequences in any order.
Examples
Example 1:
Input: beginWord = "cat", endWord = "dog", wordList = ["cot","cog","dot","dog","cag"]
Output: [["cat","cot","dot","dog"],["cat","cot","cog","dog"],["cat","cag","cog","dog"]]
Explanation: There are 3 shortest sequences. Each one changes a letter 3 times:
cat -> cot -> dot -> dog
cat -> cot -> cog -> dog
cat -> cag -> cog -> dog
Example 2:
Input: beginWord = "cat", endWord = "dog", wordList = ["cot","cog","dot"]
Output: []
Explanation: "dog" is not in wordList, so no sequence can end with it.
Example 3:
Input: beginWord = "lit", endWord = "pig", wordList = ["pit","pig","pot"]
Output: [["lit","pit","pig"]]
Explanation: There is only one shortest sequence: lit -> pit -> pig.