LintCode 582: Word Break II

Word Break II 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. Return all such possible sentences. Example Example 1: Input:“lintcode”,[“de”,“ding”,“co”,“code”,“lint”] Output:[“lint code”, “lint co de”] Explanation: