Word Break II

Word Break II

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"].

--------------------thinking---------------------------

Submission Result: Runtime ErrorMore Details 

Last executed input:

"aaaaaaa", ["aaaa","aa","a"]

------------------- codes ------------------------------
   class Solution {
   public:
       vector<string> wordBreak(string s, unordered_set<string> &dict) {
           vector<int> DP[s.size()];
           if (s.size() == 0) {
               vector<string> result;
               return result;
           }
           for (int ind = 0; ind < s.size(); ind++) {
               if (dict.find(s.substr(0, ind + 1)) != dict.end()) {
                   DP[ind].push_back(-1);
               }
               for (int sub_ind = 0; sub_ind < ind; sub_ind++) {
                   if (DP[sub_ind].size() > 0 && dict.find(s.substr(sub_ind+1, ind-sub_ind)) != dict.end()) {
                       DP[ind].push_back(sub_ind);
                   }
               }
           }
           return cvrtDP(s, DP);
       }
       vector<string> cvrtDP(string s, vector<int> *DP) {
           vector<string> result;
           vector<int> tmp_path;
           stack<int> stack;
           //bug here
           //-2 should be pushed outside of loop
           stack.push(-2);
           for(int ind = 0; ind < DP[s.size()-1].size(); ind++) {
               stack.push(DP[s.size()-1][ind]);
           }
           tmp_path.push_back(s.size() - 1);
           while (stack.size() > 1) {
               int cur = stack.top();
               stack.pop();
               if (cur == -2) {
                   tmp_path.pop_back();
               } else if (cur == -1) {
                   //bug here
                   //tmp_path should add and then delete -1 if we want to finish the loop in one pass
                   tmp_path.push_back(-1);
                   string ele;
                   for (int i = tmp_path.size() - 2; i >= 0; i--) {
                       ele += s.substr(tmp_path[i+1]+1, tmp_path[i] - tmp_path[i+1]);
                       ele += " ";
                   }
                   ele.pop_back();
                   result.push_back(ele);
                   tmp_path.pop_back();
               } else {
                   tmp_path.push_back(cur);
                   stack.push(-2);
                   for (int ind = 0; ind < DP[cur].size(); ind++) {
                       stack.push(DP[cur][ind]);
                   }
               }

           }
           return result;
       }
   };

-----------------------------------please compare this with your MLE submission-----------------------------------------------------------------
class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<vector<string> > m(s.size()+1, vector<string>());
        m[s.size()].push_back("");
        for(int idx=s.size();idx>0;idx--){
            for(int i=idx-1;i>=0;i--){
                if(dict.find(s.substr(i,idx-i)) != dict.end())
                    for(string &temp:m[idx]){
                        if(idx!=s.size())
                            m[i].push_back(s.substr(i,idx-i)+" "+temp);
                        else
                            m[i].push_back(s.substr(i,idx-i));
                    }
            }
        }
        return m[0];
    }
};