WordBreak_I_RecMemo.cpp

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if(wordDict.empty()) return false;
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        int len = wordDict.size();
        vector<int> memo(s.size(), -1);
        return dfs(0, s, memo, dict);
    }
    //Here memo[i] record the result of substring[0...i] and substring[i+1... len]
    bool dfs(int start, string& s, vector<int>& memo, unordered_set<string>& dict){
        if(start == s.size()) return 1;
        if(memo[start] != -1) return memo[start];
        string subS;
        for(int i = start; i < s.size(); i++){
            subS += s[i];
            if(dict.count(subS) != 0 && dfs(i+1,s,memo,dict)){
                return memo[start] = 1;
            }
        }
        return memo[start] = 0;
    }
    
};