127. Word Ladder
A transformation sequence morphs begin_word into end_word one letter at a time. Every step swaps exactly one character, and every word produced along the way — including end_word itself — must belong to the dictionary word_list. The starting word does not have to be in the dictionary.
Your function receives begin_word, end_word, and word_list, and returns how many words the shortest transformation sequence contains, counting both endpoints. If no sequence can reach end_word, return 0.
All words have the same length and consist only of lowercase English letters.
Example 1:
Input: begin_word = "hit", end_word = "cog", word_list = ["hot", "dot", "dog", "lot", "log", "cog"]
Output: 5
Explanation: One shortest chain is hit → hot → dot → dog → cog. It uses 5 words, and no valid chain is shorter.
Example 2:
Input: begin_word = "hit", end_word = "cog", word_list = ["hot", "dot", "dog", "lot", "log"]
Output: 0
Explanation: The dictionary never contains cog, so no sequence can end there.
Constraints:
- 1 ≤ word length ≤ 10
- 1 ≤ word_list.length ≤ 5000
- begin_word, end_word, and every word in word_list share the same length
- All words consist of lowercase English letters only
- begin_word ≠ end_word
Hints:
Think of every word as a node and connect two words when they differ in exactly one position. The answer is then a shortest-path question — which classic traversal finds shortest paths in an unweighted graph?
Comparing every pair of words costs O(n² · L). Instead, from each dequeued word try all 26 letters in each of its L positions and check membership in a hash set — that is O(L² · 26) per word.
Delete a word from the set the moment you enqueue it. Revisiting a word can only produce an equal-or-longer path, and pruning keeps the queue small.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: begin_word = "hit", end_word = "cog", word_list = ["hot", "dot", "dog", "lot", "log", "cog"]
Expected output: 5