Shortest Single-Edit Transformation Chain
Migrate one config token into another by changing one character at a time, where every intermediate token must be a valid entry in an allowed dictionary. Find the length of the shortest such transformation chain.
Problem
Given begin and end words of equal length and a wordList, return the number of words in the shortest transformation sequence from begin to end, changing exactly one letter per step and requiring every intermediate word (and end) to be in wordList. Return 0 if no sequence exists. The begin word need not be in wordList.
Input
Strings beginWord and endWord, and a list of strings wordList.
Output
The number of words in the shortest sequence (including both ends), or 0.
Constraints
- 1 ≤ word length ≤ 10
- 1 ≤ wordList.length ≤ 5000
- All words same length, lowercase English.
- endWord must be in wordList for a sequence to exist.
Examples
Example 1
Input
begin="hit" end="cog" wordList=["hot","dot","dog","lot","log","cog"]
Output
5
hit → hot → dot → dog → cog has 5 words.
Example 2
Input
begin="hit" end="cog" wordList=["hot","dot","dog","lot","log"]
Output
0
'cog' is absent, so no valid sequence.