Find the shortest sequence of one-letter transformations from a start word to a target word, where every intermediate word must be valid.
Given a beginWord, an endWord, and a list of allowed words, transform beginWord into endWord by changing exactly one character at a time.
Every intermediate word must exist in the given list of allowed words. Return the number of words in the shortest valid transformation sequence, including both the start and end words. If no such sequence exists, return 0.
This is an unweighted shortest-path problem over an implicit graph whose vertices are words and whose edges connect words that differ by one character.
beginWord: starting stringendWord: target stringwordList: array of allowed stringsAll words are assumed to have the same length.
Return an integer: the length of the shortest valid transformation sequence, or 0 if the target cannot be reached.
wordList.beginWord is not required to be in wordList.endWord is not in wordList, the answer is 0.Example 1
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output
5
Explanation
One shortest sequence is: hit -> hot -> dot -> dog -> cog. The sequence length is 5.
Example 2
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output
0
Explanation
The target word "cog" is not reachable because it is not present in the allowed list.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.