Question

You are given a string of n characters $\mathit{s}\mathbf{[}\mathbf{1}\mathbf{.}\mathbf{.}\mathbf{.}\mathit{n}\mathbf{]}$, 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 document using a dictionary, which is available in the form of a Boolean function dict(.): for any string w,

$\mathbf{dict}\mathbf{\left(}\mathbf{w}\mathbf{\right)}\mathbf{=}\{\begin{array}{l}\mathrm{true}\mathrm{if}w\mathrm{is}a\mathrm{valid}\mathrm{word}\\ \mathrm{false}\mathrm{otherwise}\end{array}$

Give a dynamic programming algorithm that determines whether the string $\mathit{s}\mathbf{[}\mathbf{.}\mathbf{]}\mathbf{}$can be reconstituted as a sequence of valid words. The running time should be at most$\mathbf{O}\mathbf{\left(}{\mathbf{n}}^{\mathbf{2}}\mathbf{\right)}$ , assuming calls to dict take unit time.

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

Short answer

We are going to use dynamic programming to reconstruct the given document, by using dict() function.

Before we create our algorithm, we will define our sub-problem so:

$\mathbf{S}\mathbf{\left(}\mathbf{i}\mathbf{\right)}\mathbf{=}\mathbf{MAX}\left\{S\left(j\right):\mathrm{dict}(s[i,i+1,\dots j\left]\right)=\mathrm{true}\mathrm{AND}S(i-1)\right\}$

The$S\left(i\right)$ function means if the sub-string(s) we encounter from ‘i’ to ‘j’ is valid word according to dictionary.

And we are simultaneously we storing the previous word’s validity and checking using$S(i-1)$.

Step-by-step solution

Algorithm Implementation for Reconstitution

$S\left(j\right)=1$if the substring$s\left[1\right],s\left[2\right],\dots .,s\left[j\right]$can be reconstructed as a valid word of sequence.

$$\begin{gathered} S\left(0\right)=1 \\ for(j=1ton) \\ S\left(j\right)=0 \\ for(i=jtodown1) \\ if\left(dict\right(s[i,i+1,\dots .,j])=trueANDS(i-1)=1) \\ S\left(j\right)=1 \end{gathered}$$

end.

Since our both loops running upto n times, so the time complexity of above algorithm is:$O\left(n^2\right)$

Algorithm to produce output of valid sequence of word

Here, we going to use an array words[] that will store the valid word sequence

$$\begin{gathered} previous=0 \\ words=\left[\right] \\ for(i=1toj) \\ if(i\ne 0) \\ word=s[fromprevioustoi] \end{gathered}$$

$words=words+word$ \\ this will append the previous valid word with present valid word

$previous=i$\\ this will shift the position of variable previous to new value ‘i’

return words

This program will return the valid words in the sentence.