Word Ladder

Hard

Given beginWord, endWord, and a wordList, return the number of words in the shortest transformation sequence from begin to end (changing one letter at a time, each intermediate word in the list), or 0 if none. The count includes both endpoints.

Example 1

Input:  beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5

Example 2

Input:  beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0

Constraints

• 1 <= word length <= 10
• 1 <= wordList.length <= 5000
• All words have the same length.