Word Ladder
Prereq: BFS on Graph
Word Ladder is "A puzzle begins with two words, and to solve the puzzle one must find a chain of other words to link the two, in which two adjacent words (that is, words in successive steps) differ by one letter."
For example: COLD → CORD → CARD → WARD → WARM
Given a start word, an end word, and a list of dictionary words, determine the minimum number of steps to go from the start word to the end word using only words from the dictionary.
Input:
1start = "COLD" 2end = "WARM" 3word_list = ["COLD", "GOLD", "CORD", "SOLD", "CARD", "WARD", "WARM", "TARD"]
Output:
14
Explanation:
We can go from COLD
to WARM
by going through COLD → CORD → CARD → WARD → WARM