8. Word Ladder
Hard•
Transform beginWord into endWord by changing exactly one letter at a time. Every word after the starting word must belong to wordList, including the target. The starting word does not have to appear in the dictionary.
Return the number of words in the shortest transformation sequence, counting both the start and target. Return 0 when no sequence exists. A direct transformation therefore returns 2.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
Output: 5
Explanation: hit → hot → dot → dog → cog has five words and four transformations. No shorter sequence exists.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log"]
Output: 0
Explanation: The target is not in the dictionary.
Example 3:
Input: beginWord = "a", endWord = "c", wordList = ["a", "b", "c"]
Output: 2
Explanation: Changing one letter reaches the target directly. Intermediate alternatives are longer.
Constraints
- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- Every dictionary word has the same length as beginWord.
- All words contain only lowercase English letters.
- beginWord != endWord
- Dictionary words are unique.
Accepted3/3|Acceptance Rate100.0%