I got a Memory Limit Exceeded with a solution using DP and map. Could you help me?


  • 0
    S

    I got a Memory Limit Exceeded. I use DP and a map to solve the problem, the map records the strings found in the dictionary to the pos i. My code is as follows:

    class Solution
    {
    public:
    	vector<string> wordBreak(string s, unordered_set<string> &dict)
    	{
    	    int len = s.size();
    		vector<string> result(len + 1);
            map<int, vector<string>>  strMap;
    		vector<bool> DP(len + 1, false);
    		DP[0] = true;
    
    		for(int i = 0; i < len; ++i)
    		{
    			vector<string> tmpResult;
    			for(int j = i; j >= 0; --j)
    			{
    				string str = s.substr(j, i - j + 1);
    				if(dict.find(str) != dict.end() && DP[j])
    				{
                        if(j == 0)
    					{
    						str.append(" ");
    						tmpResult.push_back(str);  // start words
    					}
    					else
    					{
    						// append each word to its previous string
    					    result = strMap[j];
    						vector<string>::iterator it = result.begin();
    						for(; it != result.end(); ++it)
    						{
    							string tmpStr = *it;
    							tmpStr.append(str);
    							tmpStr.append(" ");
    							tmpResult.push_back(tmpStr);
    						}
    					}
    	
    					DP[i + 1] = true;
    				}
    			}
    			if(DP[i + 1])
    			    strMap.insert(pair<int, vector<string>>(i + 1, tmpResult)); 
    			    // update the map, key : char pos, val : all strings find in dictionary to pos i + 1
    		}
    
    		if(DP[len])
                return strMap[len];
    		else
    		{   
    			result.push_back("not found");
    			return result;
    		}
    	}
    };

Log in to reply
 

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