Solution Found!
You are given a string of n characters s[1 . . . n], which you believe to be a corrupted
Chapter 6, Problem 6.4(choose chapter or problem)
You are given a string of n characters \(s[1 \ldots n]\), 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
\(\operatorname{dict}(w)=\left\{\begin{array}{ll} \text { true } & \text { if } w \text { is a valid word } \\ \text { false } & \text { otherwise. } \end{array}\right.\)
(a) Give a dynamic programming algorithm that determines whether the string \(s[\cdot]\) can be reconstituted as a sequence of valid words. The running time should be at most \(O\left(n^{2}\right)\), assuming calls to dict take unit time.
(b) In the event that the string is valid, make your algorithm output the corresponding sequence of words.
Questions & Answers
QUESTION:
You are given a string of n characters \(s[1 \ldots n]\), 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
\(\operatorname{dict}(w)=\left\{\begin{array}{ll} \text { true } & \text { if } w \text { is a valid word } \\ \text { false } & \text { otherwise. } \end{array}\right.\)
(a) Give a dynamic programming algorithm that determines whether the string \(s[\cdot]\) can be reconstituted as a sequence of valid words. The running time should be at most \(O\left(n^{2}\right)\), assuming calls to dict take unit time.
(b) In the event that the string is valid, make your algorithm output the corresponding sequence of words.
ANSWER:Step 1 of 3
Let \(P(j)=1\) if the substring \(\mathrm{s}[1], \mathrm{s}[2], \ldots \ldots \ldots, \mathrm{s}[j]\) can be reconstituted as a sequence of valid words. We compute the values in order from 1 to n as follows.
Algorithm:
1: procedure RECONSTITUTE(s)
2: Initialize \(P(0)=1\)
3: for \(j=1 \text { to } n\) do
4: Initialize \(P(j)=0\)
5: for \(i=j\) down to 1 do
6: if \(d(s[i], s[i+1], \ldots ., s[j])=\) true and \(P(i-1)=1\) then
7: \(P(j)=1\)
8: end if
9: end for
10: end for
11: end procedure