题目描述：

方法1：回溯

class Solution {
public:
    bool backtrack(string s,unordered_set<string> words,int StartIndex){//从StartIndex开始截取
        if(StartIndex == s.size()) return true;

        for(int i=StartIndex;i<s.size();i++){
            string s1 = s.substr(StartIndex,i - StartIndex +1);
            if(words.find(s1) != words.end()){
                if(backtrack(s,words,++StartIndex)) return true;
            }
        } 
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words(wordDict.begin(),wordDict.end());
        return backtrack(s,words,0);
    }
};

出错，if(backtrack(s,words,++StartIndex))出错，应该是if(backtrack(s,words,i+1))

class Solution {
public:
    bool backtrack(string s,unordered_set<string> words,int StartIndex){
        if(StartIndex == s.size()) return true;

        for(int i=StartIndex;i<s.size();i++){
            string s1 = s.substr(StartIndex,i - StartIndex +1);
            if(words.find(s1) != words.end()){
                if(backtrack(s,words,i+1)) return true;
            }
        } 
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words(wordDict.begin(),wordDict.end());
        return backtrack(s,words,0);
    }
};

出错，超出时间限制

修改：使用memory数组保存每次计算的以startIndex起始的计算结果1

class Solution {
public:
    bool backtrack(string s,unordered_set<string> words,int StartIndex,vector<int> &memory){ 
        if(StartIndex == s.size()) return true;
        else if(memory[StartIndex] != -1) return memory[StartIndex];

        for(int i=StartIndex;i<s.size();i++){
            string s1 = s.substr(StartIndex,i - StartIndex +1);
            if(words.find(s1) != words.end()){
                if(backtrack(s,words,i+1,memory)) {
                    memory[StartIndex] = 1;
                    return true;
                }
            }
        } 
        memory[StartIndex] = 0;
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<int> memory(s.size(),-1);  //-1表示还没初始化
        unordered_set<string> words(wordDict.begin(),wordDict.end());
        return backtrack(s,words,0,memory);
    }
};

方法二：动态规划，转换为完全背包问题

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词

if([j, i] 子串在字典里 && dp[j]=true) 那么 dp[i] = true

注：本题是求排列数，所以先遍历背包，再遍历物品

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words(wordDict.begin(),wordDict.end());
        vector<bool> dp(s.size()+1,0);
        dp[0] = 1;
        for(int i=1;i<=s.size();i++){
            for(int j=0;j<=i;j++){
                if(dp[j] && words.find(s.substr(j,i-j))!=words.end()) dp[i] = 1;
            }
        }
        return dp[s.size()];
    }
};