Why Memory Limit Exceeded?


  • 0
    D

    Can anyone tell me why the following code generated Memory Limit Exceeded? I tested it in VS for that catsanddog string, which works.

    class Solution {
    public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
    int len = s.length();

        bool *can =new bool[len+1];
        
        can[0] = true;
        
        for (int i=1;i<len+1; i++)
        can[i]=false;
        
        vector<vector <string>> dp(len+1, vector<string>());
        dp[0].push_back("");
        string str;
        for (int i=1; i<=len; i++)
           for (int j=0;j<i;j++)
           {
               str = s.substr(j,i-j);
               if (can[j]&&dict.find(str)!=dict.end())
               {
    			   can[i]=true;
    			   string empty;
    			   if (j>0) empty = " ";
    
                   for (int idx=0; idx<dp[j].size(); idx++)
                   {
                       string n = dp[j][idx] + empty + str; 
                       dp[i].push_back(n);
                   }
               }
               
               
           }
        return dp[len];
    
    }
    

    };


Log in to reply
 

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