Dynamic Programming using C++


  • 0
    B
    class Solution {
    public:
    
    vector<bool> vec;
    vector<vector<vector<string> > > res;
    
    vector<vector<string> > search(string s, unordered_set<string>& wordDict){
        int len = s.length();
        if(vec[len])    return res[len];
        
        vector<vector<string> > v;
        if(len == 0){
            vector<string> vv;
            v.push_back(vv);
            return v;
        }
        
        for(int i = 0; i < len; i ++){
            string tmp = s.substr(0, i + 1);
            if(wordDict.find(tmp) != wordDict.end()){
                vector<vector<string> > tr = search(s.substr(i + 1), wordDict);
                    for(int j = 0; j < tr.size(); j ++){
                        tr[j].insert(tr[j].begin(), tmp);
                    }
                    
                    if(tr.size()) v.insert(v.end(), tr.begin(), tr.end());
            }
        }
        vec[len] = true;
        res[len] = v;
        return v;
    }
    
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        int m = s.length();
        for(int i = 0; i <= m; i ++) vec.push_back(false);
        
        vector<vector<string> > vv;
        for(int i = 0; i <= m; i ++) res.push_back(vv);
        
        vector<vector<string> > v = search(s, wordDict);
        vector<string> r;
        for(int i = 0; i < v.size(); i ++){
            string t = "";
            for(int j = 0; j < v[i].size(); j ++){
                t += v[i][j];
                if(j != v[i].size() - 1) t += " ";
            }
            if(t != "")
                r.push_back(t);
        }
        
        return r;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.