Zero To DSAZero To DSA
Privacy Policy
Rotting Oranges

Word Ladder

hard
Time: O(n * m * 26)
Space: O(n)

Given two words (beginWord and endWord) and a dictionary's word list, return the length of the shortest transformation sequence from beginWord to endWord. Each transformation can change only one letter.

Constraints

  • 1 <= beginWord.length <= 10
  • All words have the same length.

Examples

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