Programming Project 3 – Dynamic Programming
Programming Project 3 – Dynamic Programming
In this project, we are given a string, and we want to determine if this string can
e “split” into one or more words such that each of the words appear in the book Alice in
Wonderland. The words of the book are provided in this project in a text file. When
splitting a word, you are not allowed to drop any characters or rea
ange the order of the
characters. You can split the word as many times as you need so that each of the words
from your split are in Alice and Wonderland. If the input string is a word in the book,
then you do not need to split it, you can accept the input string as a word itself. You
output should say how many words you can split it into, and print out the resulting
words. If there are many ways to split it into words, you should output the minimum
number of splits needed.
There are several options for storing the word list, but I’d recommend using
hashing. If you are using Java, you can do this with a HashSet. If using Python, you can
use a dictionary. If using C, you could use your HashTable implementation from data
structures. You could also use a binary search tree, but this would be a bit less efficient
if you used a very large dictionary like a Scra
le word list.
Examples:
• Input: “aliceinwonderland”.
o Output: “aliceinwonderland can be split into 3 AiW words: alice in wonderland”
• Input: “suddenly”.
o Output: “suddenly can be split into 1 AiW word: suddenly”
• Input: “alicee”
o Output: “alicee cannot be split into AiW words.”
- Note that in the last example, you can split the string into “alice e”. “alice” is in the
word list, but “e” is not, and so this is an invalid splitting. Note that in the first
example, another solution would be “alice in wonder land” but that uses one
more word than the optimal solution that was given above.
**You must use a dynamic programming algorithm. The running time you should go fo
is O(n^2)**
Please provide a bash script named ‘project3.sh’ that will act similarly to a makefile.