Use c++ language You have to determine whether the stream is a string (a sentence) of valid English words, or not. For example, the stream ―uuydhllhfis does not give a string of valid words, but the stream, unleashdeadlyturtleheadsonearthplease is just the sentence: ―unleash deadly turtleheads on earth please. To your aide you have a lexicon of concise 40th century English. Given a string w, this lexicon returns true if w is a valid English word and false otherwise in O(1). Given a stream of length n i.e. n characters, describe a DP algorithm that will detect whether or not the input string is a valid English sentence. Your algorithm should also print the valid string. Beware: the future of the Earth is in your hands! • Define an optimal subproblem, E[k] •Define a recurrence to compute subproblem E[k] using smaller subproblems. • Define an array S[k] that can be used to retrieve a valid splitting of the war message into words, if one exists.
Use c++ language
You have to determine whether the stream is a string (a sentence) of valid English words, or not. For
example, the stream ―uuydhllhfis does not give a string of valid words, but the stream,
unleashdeadlyturtleheadsonearthplease is just the sentence: ―unleash deadly turtleheads on earth
please. To your aide you have a lexicon of concise 40th century English. Given a string w, this lexicon
returns true if w is a valid English word and false otherwise in O(1). Given a stream of length n i.e. n
characters, describe a DP
hands!
• Define an optimal subproblem, E[k]
•Define a recurrence to compute subproblem E[k] using smaller subproblems.
• Define an array S[k] that can be used to retrieve a valid splitting of the war message into words, if
one exists.
Step by step
Solved in 3 steps
