Why Memory Limit Exceeded?


  • 0
    Q

    For this problem, I choose to solve it by DP method. Following is my code:

    class Solution {
    public:
    	int longestValidParentheses(string s) {
    		int len = s.length();
    		if (s == "")return 0;
    		vector<int> col(len, 0);
    		vector<vector<int> > L(len, col);
    		for (int i = 0; i < len; i++) {
    			for (int j = 0; j < len; j++)
    			if (j - i == 1 && s[i] == '(' && s[j] == ')')L[i][j] = 2;
    			else
    				L[i][j] = 0;
    		}
    		for (int j = 2; j < len; j++)
    		for (int i = j - 2; i > -1; i--) {
    			if (s[j] == ')' && s[i] == '(') {
    				int max = L[i + 1][j] > L[i][j - 1] ? L[i + 1][j] : L[i][j - 1];
    				L[i][j] = max;
    				if (max == (j - i - 1))L[i][j] += 2;
    			}
    			else if (s[j] == ')' && s[i] == ')')
    				L[i][j] = L[i + 1][j];
    			else if (s[j] == '(' && s[i] == '(')
    				L[i][j] = L[i][j - 1];
    			else
    				L[i][j] = L[i + 1][j - 1];
    		}
    		return L[0][len - 1];
    	}
    };
    

    I tried some test cases and they all passed. But I got Memory Limit Exceeded after submitting.
    Maybe the vector L is two big? Or for this question, the only accepted solution is the one that do not use DP?


  • 0
    A

    I met the same problem. Read the description again. It asks for substring, rather than subsequence. So DP is unnecessary.


  • 0
    E

    I use the traditional stack method but adding a few variables for sub-string concatenation.

    class Solution {
    public:
    
        struct Info
        {
            Info(char u, int p, int vp, int vl) 
                : c(u), pos(p), last_valid_pos(vp), last_valid_len(vl){};
            char c;
            int pos;
            int last_valid_pos;
            int last_valid_len;
        
        };
    
        int longestValidParentheses(string s) {
            
            if (s.size() == 0)
                return 0;
                
            int max_len = 0;
            int last_valid_len = 0;
            int last_valid_pos = -1;
            
            stack <Info> stk;
            
            for (int i = 0; i < s.size(); ++i) {
                if (stk.empty() || 
                    stk.top().c == s[i] ||
                    (stk.top().c == ')' && s[i] == '(')) {
                    stk.push(Info(s[i], i, last_valid_pos, last_valid_len));
                } else {
                    auto top = stk.top();
                    stk.pop();
                    int n = i - top.pos + 1;
                    if (top.last_valid_pos + 1 == top.pos) {
                        last_valid_len = top.last_valid_len + n;
                        last_valid_pos = i;
                        max_len = (last_valid_len > max_len ? last_valid_len : max_len);
                    }
                    else {
                        max_len = (max_len < n ? n : max_len);
                        last_valid_len = n;
                        last_valid_pos = i;
                    }
                }
            }
            return max_len;
        }
    };

Log in to reply
 

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