Description
Given two words beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists. Each adjacent pair of words differs by a single letter.
Examples
Input:
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]Output:
5Explanation:
One shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", which is 5 words long.
Input:
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]Output:
0Explanation:
The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
Input:
beginWord = "cold", endWord = "warm", wordList = ["cold","cord","card","ward","warm","wart","want","wind","find"]Output:
5Explanation:
One shortest transformation is "cold" -> "cord" -> "card" -> "ward" -> "warm", which is 5 words long. Note that there might be other paths like going through "wart", but they would be longer or equal in length.
Constraints
- •
1 ≤ beginWord.length ≤ 10 - •
endWord.length == beginWord.length - •
1 ≤ wordList.length ≤ 5000 - •
wordList[i].length == beginWord.length - •
beginWord, endWord, and wordList[i] consist of lowercase English letters. - •
beginWord != endWord - •
All the words in wordList are unique.