Why my code get result "Memory Limit Exceeded"


  • 0
    Y

    In this problem, I use recursive method to calculate the content in parenthesis, then add up all the numbers and results step by step. I run this code on local machine, it works, but when using OJ, it shows "Memory Limit Exceeded". Anyone can help me with it?

    class Solution {
    public:
        int calculate(string s) {
            if(!s.length()) return 0;
            vector<int> ans;
            ans = cal(s,0);
            return ans[0];
        }
        
        vector<int> cal(string str, int stpos) {
            long int subsum = 0;
            vector<int> ans;
            int i = 0;
            int currsign = 1;
            for(i = stpos; i < str.length(); i++) {
                char ch = str[i];
                switch(ch) {
                    case ' ': {break;}
                    case '+': {currsign = 1; break;}
                    case '-': {currsign = -1; break;}
                    case '(': {
                        vector<int> ans1;
                        ans1 = cal(str,i + 1);
                        subsum += ans1[0]*currsign;
                        i = ans1[1];
                        break;
                    }
                    case ')': {
                        vector<int> ans2;
                        ans2.push_back(subsum);
                        ans2.push_back(i);
                        return ans2; break;
                    }
                    default: {
                        if((ch >= '0')&&(ch <= '9')) {
                            int j = i;
                            long int currnum = ch - '0';
                            while((str[j + 1] >= '0')&&(str[j + 1] <= '9')) {
                                currnum = currnum * 10 + str[j + 1] - '0';
                                j++;
                            }
                            subsum += currnum * currsign;
                            i = j;
                        }
                    }
                }
            }
            ans.push_back(subsum);
            ans.push_back(i);
            return ans;
        }
    };

  • 0

    The reason you are exceeding the memory limit is because every time the recursive function cal is called, you are making a copy of str. Note that str could be a very long string. Just pass str as a const reference:

    vector<int> cal(const string &str, int stpos);

  • 0
    Y

    Yes, you are right. Thank you very much!


Log in to reply
 

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