3. corrupted text. you are given a string of n characters s[1..n], which you believe to be a corrupted text document in which all punctuation has vanished (so that it looks something like ""). you wish to reconstruct the document using a dictionary, which is available in the form of a boolean function dict(·): for any string w, dict(w) = true if w is a valid word, and dict(w) = false otherwise. give an algorithm that determines whether or not the string s can be reconstituted as a sequence of valid words. the running time should be at most o(n2), assuming calls to dict take unit time. hint: use dynamic programming. approach the problem as in problem 2: first design a recursive algorithm, identify the subproblems, and then memoize (you don’t need to give an iterative algorithm).