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.
输入描述:
s ="catsanddog" dict ="cat", "cats", "and", "sand", "dog"
输出描述:
[cats and dog, cat sand dog]
示例1
输入
s ="catsanddog"
dict ="cat","cats","and","sand","dog"