A word ladder is a sequence of words [w0, w1, ..., wn] such that each word wi in the sequence is obtained by changing a single character in the word wi-1. All words in the ladder must be valid English words.
Given two input words and a file that contains an ordered word list, implement a routine (e.g., find_shortest_ladder(word1, word2, wordlist)) that finds the shortest ladder between the two input words. For example, for the words cold and warm, the routine might return:
("cold", "cord", "core", "care", "card", "ward", "warm")
However, there's a shortest ladder: ("cold", "cord", "card", "ward", "warm").
Givens:
- All words in the list have the same length.
- All words contain only lowercase alphabetical characters.
- There are no duplicates in the word list.
- The input words aren't empty and aren't equal but they have the same length as any word in the word list.
Requirements:
-
The routine must return a list of the words in the ladder if it exists. Otherwise, it returns an empty list.
-
If any of the input words is the wrong length (i.e., its length is different to a random from the word list) or isn't in the word list, return an empty list.
Sample file(s):
- Five-letter words - Must be sorted.
- Moby Word Lists(e.g., COMPOUND.TXT) - Words have varying lengths so they need to be first categorized into files only containing 1-letter, 2-letter, ..., n-letter words.