All Shortest Token Transformation Chains
A token can mutate one character at a time, but every intermediate token must exist in an approved vocabulary. Enumerate every shortest mutation chain from a begin token to an end token.
Problem
Given two words beginWord and endWord and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord. Each adjacent pair of words differs by exactly one letter, and every intermediate word must be in wordList. Return an empty list if no such sequence exists. beginWord need not be in wordList.
Input
Strings beginWord and endWord of equal length, and a list wordList of words.
Output
A list of transformation sequences (each a list of words).
Constraints
- 1 <= beginWord.length <= 7
- endWord.length == beginWord.length
- 1 <= wordList.length <= 500
- All words are lowercase and the same length.
Examples
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"]]
Two distinct shortest chains of length 5.
Example 2
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output
[]
endWord 'cog' is absent, so no sequence exists.