Word Ladder
HardGraphs
You are given two words, begin_word and end_word, and a dictionary word_list. A transformation sequence is a list of words that starts with begin_word and ends with end_word, where:
- each consecutive pair of words differs in exactly one letter position, and
- every word after
begin_word(includingend_word) is inword_list.
begin_word itself does not need to be in word_list.
Return the number of words in the shortest transformation sequence, counting both begin_word and end_word. If no such sequence exists (including when end_word is not in word_list), return 0.
Example 1
- Input:
- begin_word = "lead", end_word = "gold", word_list = ["load", "lend", "goad", "bold", "gold"]
- Output:
- 4
- Explanation
- The shortest sequence is
lead -> load -> goad -> gold, changing one letter at a time. It has 4 words.lendandboldare in the list but do not lead to a shorter sequence.
Example 2
- Input:
- begin_word = "mint", end_word = "mild", word_list = ["mind", "mine", "mile"]
- Output:
- 0
- Explanation
mildis not inword_list, so no sequence can end there and the answer is0.
Example 3
- Input:
- begin_word = "cat", end_word = "cot", word_list = ["cut", "cot", "dot"]
- Output:
- 2
- Explanation
catandcotdiffer only in the middle letter, so the sequence is justcat -> cot, which has 2 words.
Constraints
- 1 ≤
begin_word.length≤ 10 end_word.length == begin_word.length, and every word inword_listhas that same length- 1 ≤
word_list.length≤ 5000 - All words consist of lowercase English letters
begin_word != end_word, and the words inword_listare unique