Dynamic Programming - Restoring white space between words in a file

[MattS134]

All the white space among words in a text file was lost. Write a C++ program which using dynamic programming to get all of the possible original text files (i.e. with white spaces between words) and rank them in order of likelihood with the best possible runtime.

You have a text file of dictionary words and the popularity class of the word (words are listed from popularity 1-100 (being most popular words), 101-200, etc)

- Input is a text file

- Output should be a series of files, each containing one the possible original documents and one document containing the ranking of likelihood of the outputs

- Use the right data structure for storing the data structure in memory, as this will impact the runtime

- Only dictionary words will be in the input text file

- Punctuation such as: . ? ! ; should be handled by program

- Remove words with non-English letters from dictionary

- Remove all the single letter words except for 'I' , 'A', and 'a' from dictionary or handle them in another way. (Important so there aren't infinite possible solutions)

To Test:

- Create text files using words in the dictionary. The ranking of outputs is in part based on the popularity class of the words used

I know how to use filestreams to store information from the file, but I'm not sure what data structure to use to store the dictionary for max efficiency
Also not sure of the logic of generating multiple output text files and how to create all possible original documents

 

[.Scott]

You have a tree-walk. In each case, you will look at the start of the text and look for all possible first words. The skip past that word and repeat the process. Whenever you get to the end of the file or punctuation, you have success. So back up to the previous word and look for another. Whenever you get to a character string that cannot form a word, that string has failed to generate a solution. So, once again, back up to the previous word and look for another.