题目：

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
 注意你可以重复使用字典中的单词。

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

题目分析：

第一种：回溯法，超时
第二种：动态规划

代码：

回溯法

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        string temp;
        if(wordDict.size()==0)
            return false;
        return word(s, temp, wordDict, 0);
    }

    bool word(string s, string& temp, vector<string>& wordDict, int start)
    {
        for(size_t i=0;i<wordDict.size();++i)
        {
            if(check(s.substr(start), wordDict[i]))
            {
                string temp2=temp;
                temp+=wordDict[i];
                start+=wordDict[i].size();
                if(temp==s)
                    return true;
                if(word(s,temp,wordDict,start))
                    return true;
                start-=wordDict[i].size();
                temp=temp2;
            }
        }
        return false;
    }

    bool check(string s, string p)
    {
        if(s.size()<p.size())
            return false;
        for(size_t i=0;i<p.size();++i)
            if(s[i]!=p[i])
                return false;
        return true;
    }
};

动态规划

class Solution {
public:
    bool check(string s, vector<string>& wordDict, int start, int end)
    {
        string t=s.substr(start,end-start+1);
        for(auto& word:wordDict)
            if(word==t)
                return true;
        return false;
    }

    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> flag(s.size(),0);
        for(size_t i=0;i<s.size();++i)
        {
            flag[i]=check(s,wordDict,0,i);
            if(!flag[i])
            {
                int j=i-1;
                while(j>=0)
                {
                    if(flag[j])
                        flag[i]=check(s,wordDict,j+1,i);
                    if(flag[i])
                        break;
                    j--;
                }
            }
        }
        return flag.back();
    }
};