Dynamic Programming $(30$ marks$)$

You are given a string of $n$ characters: $s[1$dotsn$],$ which you believe to be a corrupted text document

in which all punctuation has vanished $($so that it looks something like "itwasthebestoftimes..."$).$ You

wish to reconstruct the original document using a dictionary, which is available in the form of a

Boolean function dict$().$Foranystringw,dict$(w)returnstrueifwisavalidword$;otherwise,false

be returned.

$($a$)$ Give a dynamic programming algorithm that determines whether the

string $s[]$ can be reconstituted as a sequence of valid words. The running time should be

at most $O(n^2),$ assuming calls to dict take unit time.

$($b$)$ In the event that the string is valid, modify your algorithm to output the corresponding sequence

of words.