Why my code Memory Limit Exceeded?


  • 1
    J
    	vector<vector<string>> substrs(s.size()+1);
    	substrs[0].push_back("");
    	vector<bool> flag(s.size()+1, false);//flag[i] means from 0 to i -1 can be broken right
    	flag[0] = true;
    	for (int i = 0; i < s.size(); ++i)
    	{
    		for (int j = 0; j <= i; ++j)
    		{
    			string str = s.substr(j,i-j+1);
    			if (flag[j] && dict.find(str) != dict.end())
    			{
    				flag[i+1] = true;
    				for (int is = 0; is < substrs[j].size(); ++is)
    				{
    					string split=" ";
    					if (i == s.size()-1)
    					{
    						split = "";
    					}
    					substrs[i+1].push_back(substrs[j][is] + str + split);
    				}
    			}
    		}
    	}
    	
    	return substrs[s.size()];
    

    Please test this case. your method could be Memory Limit Exceeded. But mine can get result quickly.
    string s = "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
    string a[] = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};
    unordered_set<string> dict(a, a+sizeof(a)/sizeof(string));


  • 3
    B

    if the string s is a valid sentence, then it will take so many time to proceed and get LTE actually, so here you should check if the sentence can be breaked use algorithm like WorkBreak I, IMHO


  • 0
    W

    yes,you are right.But maybe solve Memory Limit Exceed to Accept.If the test case change to
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
    string a[] = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};
    unordered_set dict(a, a+sizeof(a)/sizeof(string));
    I think it also have Memory Limit Exceed.


Log in to reply
 

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