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 be “split” into one or more...

Dynamic Programming


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 be “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 rearrange 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. Your 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 Scrabble 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 for is O(n^2)** Please provide a bash script named ‘project3.sh’ that will act similarly to a makefile.