动态规划
对于字符串“leetcode”：
- 如果字符串"l"存在于字典中，则字符串"leetcode"能否由字典中的单词构成取决于字符串“eetcode”能否由字典中的单词构成
- 如果字符串“l”不在字典中，则判断字符串“le”是否字典中，如果在，则字符串“leetcode”能否由字典中的单词构成取决于字符串“etcode”能否由字典中的单词构成
- 如果字符串“le”也不在字典中，那么判断字符串"lee"是否在字典中，如果在，则字符串“leetcode”能否由字典中的单词构成取决于字符串"tcode"能否由字典中的单词构成
- ...
令state[i]表示字符串中从下标i开始到结尾的子串能否由字典中的单词构成。对于"leetcode"：
- state[0]就表示“leetcode”能否由字典中的单词构成
- state[2]就表示“leetcode”能否由字典中的单词构成
- state[8]就表示""能够由字典中的单词构成
假设substr(i,j)表示字符串s中下标i到下标j的子串，那么state[i] = dict.contain(substr(i,j)) && state[j + 1]
- 时间复杂度：O(n^2)（n为字符串长度）
- 空间复杂度：O(n + m)（n为字符串长度，m为字典中单词数）