Why Exceed Memory Limit?


  • 0
    D

    I tried the following solution in VS, and got the right answer for the example input. But the OJ keeps reporting "Exceed Memory Limit".

    My strategy is a DP solution, which keeps track of the valid strings of each prefix, and extend them as the prefix grows. I also did some optimization by clearing all unnecessary prefix.

    I know there may be some way to optimize more for memory, but that will sacrifice CPU performance.

    Can someone tell me what is wrong in my code?

    class Solution {
    
    typedef vector <string> string_eql_len; 
    unordered_set<string> succeeded_string_set;
        
    public:
        vector<string> wordBreak(string s, unordered_set<string> &dict) {
           
          vector<string> results;
        
        if (s.size()==0)
    		return results;
        
        vector<string_eql_len>  prefix_strings;
    	unordered_set<string>::iterator it=dict.begin();
    	int longest_word_len=0;
    	while (it!=dict.end())
    	{
    		if ((*it).size()>longest_word_len)
    		    longest_word_len=(*it).size();
    
    		it++;
    	}
        
        for (int i=0 ;i < s.size(); i++)
        {
            vector<string> a_string_eql_len;
            
            prefix_strings.push_back(a_string_eql_len);
        }
        
    	for (int i =1; i<=s.size();i++)
    	{
    		unordered_set<string>::iterator it=dict.begin();
    		string cur_string (s.begin(), s.begin()+i);
    
    		if (dict.find(cur_string)!=dict.end())
    		{
    			prefix_strings[i-1].push_back(cur_string);
    		}
    	
    		while (it!=dict.end())
    		{			
    			int prefix_len=i-(*it).size();
    
    			if (prefix_len>0)
    			{
    				string suffix (cur_string.begin()+prefix_len,cur_string.end());
    
    				if (suffix!=(*it))
    				{
    					it++;
    					continue;
    				}
    				string prefix (cur_string.begin(), cur_string.begin()+prefix_len);
    				if (prefix_strings[prefix_len-1].size()!=0)
    				{
    					succeeded_string_set.insert(cur_string);
    					
    					for (int k=0;k<prefix_strings[prefix_len-1].size();k++)
    					{
                            string stringwithspace (prefix_strings[prefix_len-1][k]);
                            stringwithspace+=" ";
                            stringwithspace+=suffix;
                            
                            prefix_strings[i-1].push_back(stringwithspace);
    					}    
                        
    				}
    			}
    
    			it ++;
    		}
    
    		if (i-longest_word_len-1>0)
    		    prefix_strings[i-longest_word_len-1].clear();
    	}
    
    	return prefix_strings[prefix_strings.size()-1];
    }
    };

  • 0
    S

    Hi @deepblue, thanks for your post. I just update your code format. Please pay attention next time.


  • 0
    D

    Sure. I got it. Thanks.


Log in to reply
 

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