You want to change the word beginWord into the word endWord, one letter at a time. You can use only the words in the list wordList as steps. beginWord does not need to be in the list.
A path looks like beginWord -> s1 -> s2 -> ... -> sk. Two neighbours on the path differ in exactly one letter. Every si must be in wordList, and sk must be endWord.
Return the number of words on the shortest such path, counting beginWord and endWord. If there is no path, return 0.
Examples
Example 1:
Input: beginWord = "cold", endWord = "warm", wordList = ["cord","card","ward","warm","worm","word","corm"]
Output: 5
Explanation: One shortest path is cold -> cord -> card -> ward -> warm. It has 5 words.
Example 2:
Input: beginWord = "cold", endWord = "warm", wordList = ["cord","card","ward","worm","word","corm"]
Output: 0
Explanation: "warm" is not in the list, so it cannot be reached.
Example 3:
Input: beginWord = "tap", endWord = "top", wordList = ["top"]
Output: 2
Explanation: One change is enough: tap -> top. The path has 2 words.