Subtle difference but solve the "Memory Limit Exceeded"...why???


  • 0
    C

    Here is my code:

    class Solution {
    public:
        unordered_map<string,vector<int>>rec;
        vector<int> diffWaysToCompute(string input) 
        {
        	int s=0;
        	vector<int>res;
        	string s1,s2;
        	while(input[s]!='\0')
        	{
        		if(!isdigit(input[s]))                     
        		{
        			s1 = input.substr(0,s);
                            s2 = input.substr(s+1);
        			if(rec.find(s1) == rec.end())
        				rec[s1] = diffWaysToCompute(s1);    
        			
        			if(rec.find(s2) == rec.end()) 
        				rec[s2] = diffWaysToCompute(s2);    
        			for(auto &a:rec[s1])
        				for(auto &b:rec[s2])
        					res.push_back(input[s]=='+'?a+b:input[s]=='-'?a-b:a*b);
        		}
        		++s;                           
        	}
        	return res.empty()?vector<int>(stoi(input)):res;           
        }
    };
    

    I got a MLE. And then I found another similar solution which is just little different from mine but can get AC. I am really confused. Who can help me by explaining the problem? The following is the other solution from Gcdofree :

    class Solution {
    public:
        vector<int> diffWaysToCompute(string input) {
            unordered_map<string, vector<int>> dpMap;
            return computeWithDP(input, dpMap);
        }
    
        vector<int> computeWithDP(string input, unordered_map<string, vector<int>> &dpMap) {
            vector<int> result;
            int size = input.size();
            for (int i = 0; i < size; i++) {
                char cur = input[i];
                if (cur == '+' || cur == '-' || cur == '*') {
                    // Split input string into two parts and solve them recursively
                    vector<int> result1, result2;
                    string substr = input.substr(0, i);
                    // check if dpMap has the result for substr
                    if (dpMap.find(substr) != dpMap.end())
                        result1 = dpMap[substr];
                    else
                        result1 = computeWithDP(substr, dpMap);
    
                    substr = input.substr(i + 1);
                    if (dpMap.find(substr) != dpMap.end())
                        result2 = dpMap[substr];
                    else
                        result2 = computeWithDP(substr, dpMap);
    
                    for (auto n1 : result1) {
                        for (auto n2 : result2) {
                            if (cur == '+')
                                result.push_back(n1 + n2);
                            else if (cur == '-')
                                result.push_back(n1 - n2);
                            else
                                result.push_back(n1 * n2);
                        }
                    }
                }
            }
            // if the input string contains only number
            if (result.empty())
                result.push_back(atoi(input.c_str()));
            // save to dpMap
            dpMap[input] = result;
            return result;
        }
    };
    

  • 1

    The problem is vector<int>(stoi(input)), which should be vector<int>(1, stoi(input)) or vector<int>{stoi(input)}.

    Btw, your solution doesn't even compile, there's a } too much.


  • 0
    C

    wow, you indeed are true. I ignored the vector's initialization. Thanks for your help!


Log in to reply
 

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