The Problem
In this homework, we will solve a puzzle that involves a list of words. You will be given a long list (English) words. Then, you will be given two words A and B and be asked if you can start from A and transform it to B by a series of one-character substitutions, one character insertion or one character deletions, and if so, output the corresponding sequence of words. Note that all intermediate words must be in the list of words given. For instance, we can convert bleed to blood by going through a sequence of transformations giving us the sequence of words bleed, blend, blond, blood. We can also convert can into pale by going through a sequence of words can, man, mane, male, pale.
The Input and the Output
You will read from a file called words.txt the words that you will use as your database. The words will not be in any particular order and may contain characters such as “-” or apostrophe (‘) – these should not cause any problems. Each word will be in a separate line in the file. All the characters will be in lowercase (i.e., no capital letters). Once the file is read and processed, you will then go into a loop that does the following:
1. Read two words from the standard input (cin). The words will be separated by a space character.
2. If the first word starts with the character ‘*’ then exit the loop and terminate the program.
3. Make sure both words are in the list; print an error message if either one is not in the list
4. If both words are in the list, find out if you can transform the first word into the second by a sequence of one letter substitutions, insertions, and deletions. You should find the shortest sequence of such transformations. Print a suitable error message if no sequence of one letter transformations exists.
5. If there is such a sequence then, print the first word, the sequence of intermediate words and the last word along with the transformations that indicates what you do to the previous word to find the current word, one word to a line. For example, for the 2nd example above, your output should look like the following
can
man (change c at position 1 to m) mane (insert e after position 3) male (change n at position 3 to l) pale (change m at position 1 to p)
In the case of adding a character at the beginning of a word, for example, when going from the word ree to tree, print the following output:
tree (insert t after position 0)
For deletion you should write something like “(delete m at position 4)”, etc.
