|
Size: 1680
Comment:
|
Size: 870
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 8: | Line 8: |
| * changing one letter, e.g. ''barn→born'' * adding or removing one letter, e.g. ''band→brand'' |
1. changing one letter, e.g. ''barn→born'' 1. adding or removing one letter, e.g. ''band→brand'', and ''heart→hear'' |
| Line 15: | Line 15: |
| /* {{{ Your assignment is to write a program that computes the longest word ladder(s) that can be built from a set of words given on stdin. The output of your program is the maximum length ordered word ladder, together with all the ordered word ladders that have this length. You should also a complexity analysis (of time) using Big-oh notation. |
At the heart of the assignment is a function that compares 2 strings and returns ''true'' if the strings satisfy one of the 2 conditions above, and ''false'' otherwise. This function could have the signature: {{{#!cplusplus bool areOwl(char *, char *) |
| Line 21: | Line 20: |
The following conditions apply to the input: * it may be empty * the words are alphabetically ordered, and must be lower case (''a-z'') * no word is more than 19 letters * there will be no more than 1000 words * there is no punctuation or digits in the input Some comments about the programming: * There are no restrictions on using arrays. * You should use ADTs, in particular stack, queue and graph ADTs, if possible. * Call your source program ''ladders.c'' (for submission purposes). * In ''ladders.c'' include the statement {{{#!cplusplus #include "complexity.h" }}} This header file should contain the complexity analysis as a comment (hence use simple text). Obviously this header file should be submitted as well. */ |
Write such a function. |
Contents
Assignment 2: Ordered Word Ladders
An ordered word ladder is an alphabetically-ordered sequence of words where each word in the sequence differs from its predecessor by:
changing one letter, e.g. barn→born
adding or removing one letter, e.g. band→brand, and heart→hear
The following are examples of word ladders of different length:
ban→bar→boar→boat→goat, length 5
cab→can→cane→dane→date→mate→mite→site→size, length 9
At the heart of the assignment is a function that compares 2 strings and returns true if the strings satisfy one of the 2 conditions above, and false otherwise. This function could have the signature:
1 bool areOwl(char *, char *)
Write such a function.