Q36

Given a string s and a dictionary of words dict, add spaces in s to
construct a sentence where each word is a valid dictionary word.