Description
Given two words beginWord and endWord, and a dictionary wordList, find all shortest transformation sequences from beginWord to endWord. Each word must change one letter at a time and must be in wordList.
Examples
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"][["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]Two shortest paths of length 5.
beginWord = "cat", endWord = "dog", wordList = ["bat","cot","cog","dog","dot","bog"][["cat","cot","cog","dog"],["cat","bat","bog","dog"]]There are two shortest transformation paths of length 4. Path 1: cat→cot (change 'a' to 'o')→cog (change 't' to 'g')→dog (change 'c' to 'd'). Path 2: cat→bat (change 'c' to 'b')→bog (change 'a' to 'o')→dog (change 'b' to 'd'). Both paths have exactly 3 intermediate transformations.
beginWord = "red", endWord = "tax", wordList = ["ted","tex","red","tax","tad","den","rex","pex"][["red","ted","tad","tax"],["red","ted","tex","tax"]]Two shortest transformation sequences exist with length 4. Path 1: red→ted (change 'r' to 't')→tad (change 'e' to 'a')→tax (change 'd' to 'x'). Path 2: red→ted (change 'r' to 't')→tex (change 'd' to 'x')→tax (change 'e' to 'a'). Both converge at 'ted' then diverge through different intermediate words.
Constraints
- •
1 ≤ beginWord.length ≤ 5 - •
beginWord.length == endWord.length - •
1 ≤ wordList.length ≤ 500