$***3.$ You are given a string of $n$ characters $c_1{c}_{2}cdots{c}_n,$ which you believe to be a corrupted text document in which all punctuations have vanished $($so that it looks something like $"$ itwasthebestoftimes. $.").$ You wish to reconstruct the document using a dictionary, which is available in the form of a Boolean function dict$()$ : for a string $w,$

dict$(w)=\{\begin{array}{ccc}& \text{t}\text{r}\text{u}\text{e}ifwis\text{a}\text{v}\text{a}\text{l}\text{i}\text{d}\text{w}\text{o}\text{r}\text{d}& \\ & \text{f}\text{a}\text{l}\text{s}\text{e}\text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\text{.}& \end{array}$

$($a$)$ Give a dynamic programming algorithm that determines whether the string $c_1{c}_{2}cdots{c}_n$ can be reconstituted as a sequence of valid words. The running time should be $O(n^2),$ assuming calls to dict$(w)$ take unit time.

$($b$)$ In the event that the string is valid, make your algorithm output the corresponding sequence of words.