Why Memory Limit Exceeded?

• 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?

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

• 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;
}
};``````

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