给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例1
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例2
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
示例3
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
该问题采用动态规划解法。考虑将原问题拆解为两个子问题，以"leetcode"为例，原问题为s，拆分成的两个子问题为"leet"，
为"code"，如果
和
都有解，那么原问题s也有解，s还可以拆分成"lee"和"tcode"，在拆分成的这么多子问题中，只要任意一组子问题有解，那么s就有解。
直接采用暴力拆解会重复计算很多子问题，如计算"lee"和"leet"的子问题。因此采用动态规划避免重复求解子问题。求解时，先初始化长度为s.length()+1的dp数组，当字符串为空时，默认为有解，因此dp[0]为true，其它的都先初始化为false。假设当前求解的字符串长度为i，字符串的分割点为j，即字符串被分成s(0,j)和s(j+1,i)两个部分，s(0,j)即为dp[j]，在之前的结果中可以直接取到，因此只需要再求wordDict中是否包含s(j+1,i)。当dp[j]为true并且wordDict包含s(j+1,i)时，dp[i]为true。从这个计算过程也可以明显看出，在求解过程中省去了重复计算子问题s(0,j)。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp;
dp.push_back(true);
for(int i=1;i<=s.size();i++) dp.push_back(false);
for(int i=1;i<=s.size();i++){
for(int j=0;j<i;j++){
auto match = find(wordDict.begin(),wordDict.end(),s.substr(j,i-j));
if(match != wordDict.end() && dp[j]){
dp[i] = true;
}
}
}
return dp[s.size()];
}
};
