Config Migration Ladder
A config schema must migrate from one fingerprint to another one character at a time, and every intermediate fingerprint has to be a known-valid schema in the registry. Find the shortest such migration chain.
Problem
Given a beginWord, an endWord, and a wordList of equal-length lowercase strings, return the number of words in the shortest transformation sequence from beginWord to endWord, where each step changes exactly one character and every intermediate word exists in wordList. Return 0 if no sequence exists. The sequence length counts both endpoints.
Input
Two strings beginWord and endWord, and an array wordList. All words have the same length L (1 ≤ L ≤ 10) and consist of lowercase letters. 1 ≤ wordList.length ≤ 5000.
Output
An integer — the length of the shortest sequence, or 0 if none.
Constraints
- All words have identical length
- beginWord need not be in wordList; endWord must be for a valid answer
- Each step differs by exactly one character
Examples
Example 1
Input
begin = "hit", end = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output
5
hit → hot → dot → dog → cog uses 5 words.
Example 2
Input
begin = "hit", end = "cog", wordList = ["hot","dot","dog","lot","log"]
Output
0
endWord 'cog' is not in the list, so no sequence reaches it.