WordBreak_I_Rec.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();
        return dfs(0, s, dict);
    }
    bool dfs(int start, string& s, unordered_set<string>& dict){
        if(start == s.size()) return 1;
        string subS;
        for(int i = start; i < s.size(); i++){
            subS += s[i];
            if(dict.count(subS) != 0 && dfs(i+1,s,dict)){
                return 1;
            }
        }
        return 0;
    }
};