A transformation sequence from beginWord to endWord changes one letter at a time, and every word after beginWord must appear in wordList.
Return the number of words in the shortest such sequence, counting both beginWord and endWord, or 0 if no sequence exists.
Examples
Example 1
- Input
- beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
- Output
- 5
- Why
- hit → hot → dot → dog → cog.
Example 2
- Input
- beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log"]
- Output
- 0
- Why
- "cog" isn't in the word list, so it can't be reached.
Constraints
1 <= beginWord.length <= 10- All words have the same length and contain only lowercase English letters.
1 <= wordList.length <= 5000beginWordandendWordare different.