方法1：动态规划
1.1 错误1
无法解决诸如(())的问题。 要考虑到当前碰到右括号后，前面的是左括号还是右括号，然后分别进行处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
int l = 0;
vector<int> dp(n);
int ret = 0;
for(int i=0; i<n; ++i){
if(s[i] == '('){
++l;
continue;
}
if(l){
--l;
dp[i] = 2;
if(i-2 >= 0) dp[i] += dp[i-2];
ret = max(ret, dp[i]);
}
}
return ret;
}
};
|
1.2 错误2
无法解决诸如()(())的问题。
*****() 好解决直接 dp[i] += dp[i-2];*****)) 需要额外判断找到与当前右括号i对应的左括号t，然后t的左边要继续判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
int l = 0;
vector<int> dp(n);
int ret = 0;
for(int i=0; i<n; ++i){
if(s[i] == '('){
++l;
continue;
}
if(l){
--l;
dp[i] = 2;
if(s[i-1] == '(' && i-2 >= 0) dp[i] += dp[i-2];
else if(s[i-1] == ')') dp[i] += dp[i-1];
ret = max(ret, dp[i]);
}
}
return ret;
}
};
|
1.3 正确答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
int l = 0;
vector<int> dp(n);
int ret = 0;
for(int i=0; i<n; ++i){
if(s[i] == '('){
++l;
continue;
}
if(l){
--l;
dp[i] = 2;
if(s[i-1] == '(' && i-2 >= 0) dp[i] += dp[i-2];
else if(s[i-1] == ')'){
dp[i] += dp[i-1];
if(i-dp[i]>=0)
dp[i] += dp[i-dp[i]];
}
ret = max(ret, dp[i]);
}
}
return ret;
}
};
|
1.4 官方的DP（LC官方）(Elegant)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
vector<int> dp(n, 0);
int res = 0;
for(int i=1; i<n; ++i){
if(s[i] == '(') continue;
if(s[i-1] == '('){
if(i-2 < 0) dp[i] = 2;
else dp[i] = dp[i-2] + 2;
}else{
if(i-dp[i-1]-1>=0 && s[i-dp[i-1]-1] == '('){
dp[i] = dp[i-1] + 2;
if(i-dp[i-1]-2 >= 0)
dp[i] += dp[i-dp[i-1]-2];
}
}
res = max(res, dp[i]);
}
return res;
}
};
|
方法2：栈（LC官方）
保持栈底元素为当前已经遍历过的元素中 「最后一个没有被匹配的右括号的下标」 需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为 -1−1 的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
stack<int> stk;
stk.push(-1);
int res = 0;
for(int i=0; i<n; ++i){
if(s[i] == '(') stk.push(i);
else{
stk.pop();
if(stk.empty())
stk.push(i);
else
res = max(res, i-stk.top());
}
}
return res;
}
};
|
方法3：贪心（LC官方）
利用两个计数器l和r，从左到右遍历字符串，遇到左括号则l加1，遇到右括号则r加1；当l和r相等时更新最长长度，当r>l时将l和r置0
这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，这种时候最长有效括号是求不出来的。
解决的方法也很简单，我们只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来：当r<l时将l和r置0。
这样我们就能涵盖所有情况从而求解出答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int longestValidParentheses(string s) {
int l = 0, r = 0;
int res = 0;
for(int i=0; i<s.size(); ++i){
if(s[i] == '(') ++l;
else ++r;
if(l == r) res = max(res, l + r);
else if(r > l) l = r = 0;
}
l = r = 0;
for(int i=s.size()-1; i>=0; --i){
if(s[i] == '(') ++l;
else ++r;
if(l == r) res = max(res, l + r);
else if(l > r) l = r = 0;
}
return res;
}
};
|