Hard
Quiz
#127 Word Ladder
APPROACH
A transformation sequence from beginWord to endWord using dictionary wordList forms the chain beginWord -> s1 -> s2 -> ... -> sk satisfying:
- Each adjacent word pair differs by exactly one letter.
- Every intermediate word si must appear in wordList. The beginWord need not be in wordList.
- sk == endWord
Return the number of words in the shortest such sequence, or 0 if no valid sequence exists.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
1 of 4
1:00
What is the optimal approach for this problem?