Word Ladder
Hard · graph traversal
You are given a starting word begin_word, a target word end_word and a list of allowed words word_list. All of them have the same length and use lowercase English letters.
You turn the starting word into the target by a chain of words. In each step you change exactly one letter of the current word (the letter must become a different letter, and you may not add, remove or reorder letters). The word you get must be in word_list, otherwise the step is not allowed.
The starting word does not have to be in word_list, but the target word must be, otherwise no chain exists. The list may contain the same word more than once.
Return the number of words in the shortest chain, counting both begin_word and end_word. If no chain exists, return 0. The two words are always different.
Examples
Example 1
Input: begin_word = "lead", end_word = "gold", word_list = ["load", "goad", "gold", "road", "lend"]
Output: 4
One shortest chain is "lead" -> "load" -> "goad" -> "gold", which has 4 words.
Example 2
Input: begin_word = "lead", end_word = "gold", word_list = ["load", "goad", "road"]
Output: 0
"gold" is not in the list, so it can never be reached.
Example 3
Input: begin_word = "cat", end_word = "cot", word_list = ["cot", "dot"]
Output: 2
Changing the single letter "a" to "o" reaches the target at once, so the chain is just "cat" -> "cot".
Constraints
- 1 <= len(begin_word) <= 10
- 1 <= len(word_list) <= 2000
- len(end_word) == len(begin_word) and len(word_list[i]) == len(begin_word)
- begin_word, end_word and every word in word_list use lowercase English letters only.
- begin_word != end_word