You are given a message as a string of n characters s[1..n]. But the string has been corrupted and all punctuation and white space characters are missing. For example: itwasthebestoftimesitwastheworstoftimes. You want to reconstruct the message using a dictionary available in the form of a Boolean function:

dict(w) which evaluates to true if and only if w is a valid word.

1. Give a dynamic programming algorithm which determines if a given string s[] can be broken into a sequence of valid words. Your algorithm should be O(n2)with the assumption that calls to dict() take constant time. Also, In the event that the string is valid, make your algorithm produce the corresponding sequence of words.