[leetcode] Word Break II

Dynamic Programming give a lower bound for the Recursion. Even though do the pruning, it won't be faster than Dynamic Programming!!!

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

The first try is time limit exceed with input as:

string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";

["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"]
My Code:

 vector wordBreak(string s, unordered_set &dict) {
        vector pos;
        vector res;
        if(dict.empty()) return res;
        int n = s.length();
        if(s.empty()){
            res.push_back(" ");
            return res;
        }
        for(int len = 1; len <= n; len++){
            if(dict.find(s.substr(0, len)) != dict.end())
                pos.push_back(len);
        }
        for(int i = 0; i < pos.size(); i++){
            vector curp = wordBreak(s.substr(pos[i], n - pos[i] + 1), dict);
            if(curp.empty()) continue;
            else{
                for(int j = 0; j < curp.size(); j++){
                    string curs = s.substr(0, pos[i]) + " " + curp[j];
                    res.push_back(curs);
                }
            }
        }
        return res;
}

================================================================================

Then I used wordbreak test on WordBreak I to pruning. When there is no valid word break, do the pruning.

 bool wordCheck(string s, unordered_set &dict) {
        if(s.empty() || dict.empty()) return false;
        int n = s.length();             
        bool table[n];              
        memset(table, 0, sizeof(table));                   
        for(int i = 0; i < n; i ++){
            if(dict.find(s.substr(0, i+1)) != dict.end()) {
                table[i] = true;
                continue;
            }
            for(int j = 0; j < i ; j++){
                if(table[j] && dict.find(s.substr(j+1, i-j)) != dict.end()){            
                    table[i] = true;
                    break;
                }
            }
        }
        return table[n-1];
    }                                                              
  vector wB(string s, unordered_set &dict) {         
        vector res;
        if(dict.empty()) return res;
        int n = s.length(); 

                                       
        if(s.empty()){                                             
            res.push_back(" ");                                    
            return res;
        }                                                          
        // Pruning!!!!! The order is important!!!
        if(!wordCheck(s, dict)) return res;
        for(int len = 1; len <= n; len++){
            vector curp;
            if(dict.find(s.substr(0, len)) != dict.end())
                curp = wB(s.substr(len, n - len + 1), dict);
            
                if(curp.empty()) continue;
                else{
                  for(int j = 0; j < curp.size(); j++){
                    string curs = s.substr(0, len) + " " + curp[j];
                    res.push_back(curs);
                  }
                }
        }
    return res;
  }
  vector wordBreak(string s, unordered_set &dict){
    vector res = wB(s, dict);                              
    for(int i = res.size()-1; i>=0; --i){                          
        while(res[i].back() == ' ')
            res[i].erase(res[i].size()-1);
    }
    return res;

  }