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.

Step by step solution

01

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)$

02

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.

Unlock Step-by-Step Solutions & Ace Your Exams!

• Full Textbook Solutions

  Get detailed explanations and key concepts

• Unlimited Al creation

  Al flashcards, explanations, exams and more...

• Ads-free access

  To over 500 millions flashcards

• Money-back guarantee

  We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!