Given two words, beginWord and endWord, and a dictionary wordList, find all shortest transformation sequences from beginWord to endWord. A transformation sequence is a list of words where each adjacent pair differs by exactly one letter, and every word after the first must belong to wordList.
If no such sequence exists, return an empty list.
Input:
beginWord: a string of lowercase letters.endWord: a string of lowercase letters.wordList: a list of unique strings, all lowercase letters.Output:
beginWord and ending with endWord.Examples:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Both sequences are length 5, which is the minimum possible. Starting from "hit", changing to "hot" is the only one-letter step. From "hot" you can go to "dot" (then "dog" → "cog") or "lot" (then "log" → "cog").
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
[]
"cog" is missing from the dictionary, so the transformation cannot be completed.
Constraints:
wordList is unique.beginWord is not present in wordList.endWord is present in wordList.Follow-up: Can you also output the sequences in lexicographical order? Discuss how that changes your approach.