问题描述：
题目：Leetcode第139题
难度：中等
给你一个字符串 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
提示：
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同
BFS：
层层遍历
BFS一般不需要递归，只需要使用一个队列记录每一层需要记录的值即可。BFS中在截取 的时候，如果截取的子串存在于字典中，我们就要记录截取的位置，到下一层的时候就从 这个位置的下一个继续截取，来看下代码。
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {queue<int> q;q.push(0);int len=s.size();//v 用来纪录已经访问过的位置，如果再次访问可以直接跳过vector<bool> v;v.resize(len,false);while(!q.empty()){int index=q.front();q.pop();if(index==len){return true;}//如果被访问g过，跳过if(v[index]){continue;}//true 标记被访问过的v[index]=true;for(int i=index+1;i<=len;i++){//str 表示s 中 index 到i 这一段字符串string str(s.begin()+index,s.begin()+i);if(find(wordDict.begin(),wordDict.end(),str)!=wordDict.end()){q.push(i);}}}return false;}
};动态规划：
首先确定状态变量，我们设dp[ i ] 表示前 i 个字符 是否能够有字典里的词拼出，对于dp[ i ]我们往前截取 k 个字符 ，这时若[ i-k,i]这个字符串存在于字典中，则dp[i]=dp[i-k].
我们就可以得到转移方程：
dp[i]=dp[i-k]&& find(wordDict.begin(),wordDict.end(),str1)!=wordDict.end();
k 需要我们枚举，看代码：
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {vector<bool> dp;dp.resize(s.size()+1,false);for(int i=1;i<=s.size();i++){枚举k 的值for(int k=0;k<=i;k++){//如果往前截取全部字符串，我们直接判断子串[0,i-1]//是否存在于字典wordDict中即可if(k==i){string str(s.begin(),s.begin()+i);if(find(wordDict.begin(),wordDict.end(),str)!=wordDict.end()){dp[i]=true;continue;}}string str1(s.begin()+i-k,s.begin()+i);if( find(wordDict.begin(),wordDict.end(),str1)!=wordDict.end()){dp[i]=dp[i-k];}//如果dp[i]为true，说明前i个字符串结果拆解可以让他的所有子串//都存在于字典wordDict中，直接终止内层循环，不用再计算dp[i]了。if(dp[i]){break;}}}return dp[s.size()];}
};
