|
Size: 468
Comment:
|
Size: 1068
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 13: | Line 13: |
| The following are examples of word ladders of different length: * ''big→bit→bat→boat'' * ''cold→cord→word→warm'' |
The following are examples of word ladders of different length (that could each easily be made longer): * ''big→bit→bat→boat'', length 4 * ''cold→cord→word→ward→warm'', length 5 * ''line→fine→five→dive→live→like→lake→take→bake→cake→came→fame'', length 12 {{{ Your assignment is to write a program that computes the longest word chain(s) that can be built from a set of words given on ''stdin''. The output of your program is the maximum length of all the word chains that can be built from the input words, together with all the word chains that have this length. You should also a complexity analysis (of time) using ''Big-oh'' notation. }}} |
Contents
Assignment 2: Word Ladder
A word ladder is a sequence of words
- which are in alphabetic order
- each word in the sequence differs from its predecessor by
changing one letter, e.g. born→barn
adding or removing one letter, e.g. band→brand
The following are examples of word ladders of different length (that could each easily be made longer):
big→bit→bat→boat, length 4
cold→cord→word→ward→warm, length 5
line→fine→five→dive→live→like→lake→take→bake→cake→came→fame, length 12
Your assignment is to write a program that computes the longest word chain(s) that can be built from a set of words given on ''stdin''. The output of your program is the maximum length of all the word chains that can be built from the input words, together with all the word chains that have this length. You should also a complexity analysis (of time) using ''Big-oh'' notation.