[Work Break II] Why forward got MLE, but backward works ?


  • 0
    Z

    HI ALL<

    I tried two different solutions, the first one got memory limit exceeded, but the second one works. please help me to figure out why.

    1 forward

    vector<string> wordBreak(string s, unordered_set<string> &dict) {

        int n = s.size();
        map<int, vector<string>> m; 
        vector<bool> can_reach (n, false);
    
        for(int i = 0; i < n; ++i){
            if(i > 0 && !can_reach[i-1]) continue;
            
            for(int len = 1; i + len <= n; ++len){
                string str = s.substr(i, len);
                
                if(dict.find(str) != dict.end()){
                    can_reach[i+len-1] = true;
                    if(i == 0) 
    					m[i+len-1].push_back(str); 
                    else{
                        for(string tmp : m[i-1]){
                            string tmp_tmp = tmp + " " + str;
                            m[i+len-1].push_back(tmp_tmp);
                        }
                    }
                }
            }
        }
    	//for(string str : m[n-1]) cout << str << endl;
        return m[n-1] ;
    
    1. backward

    vector<string> wordBreak(string s, unordered_set<string> &dict) {

         vector<vector<string>> vv (s.size(), vector<string> ());
        for(int i = s.size()-1; i >= 0; i--){
            for(int j = i; j < s.size(); j++){
                string tmp = s.substr(i, j-i+1);
                if(dict.find(tmp) != dict.end()){
                    
                    vector<string> vec;
                    if(j == s.size()-1){
                        vec.push_back(tmp);
                    }
                    else{
                        // if vv[j+1] is empty, then nothing will be inserted into vv[i]
                        vec = vv[j+1];
                        for(int k = 0; k < vec.size(); k++)
                            vec[k] = tmp + " " + vec[k];
                    }
                    vv[i].insert(vv[i].end(), vec.begin(), vec.end()); // add one more solution at the tail
                }
            }
        }
        return vv[0];
    }

  • 0
    P

    I think the reason is that for dynamic programming, you are supposed to record the positions (int) rather than the strings. Backwards code got pass because the test cases happened to work under memory limits.
    Here is my AC forward code:

    class Solution {
    private:
        void backtrace(vector<string>& rst,int pos, string& s,vector<vector<int>>& dp,string output){
            if(pos==-1){
                rst.push_back(output);
                return;
            }
            string tmp=output;
            for(int i=0;i<dp[pos].size();i++){
                output=tmp;
                int start=dp[pos][i];
                if(pos==s.size()-1)
                    output=s.substr(start,pos-start+1);
                else
                    output=s.substr(start,pos-start+1)+" "+output;
                backtrace(rst,start-1,s,dp,output);
            }
        }
    public:
        vector<string> wordBreak(string s, unordered_set<string> &dict) {
            vector<vector<int>> dp(s.size(),vector<int>());
            for(int i=0;i<s.size();i++){
                for(int j=i;j>=0;j--){
                    string sub=s.substr(j,i-j+1);
                    if(dict.find(sub)!=dict.end())
                        dp[i].push_back(j);
                    }
            }
            vector<string> rst;
            backtrace(rst,s.size()-1,s,dp,"");
            return rst;
        }
    };

Log in to reply
 

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