32. 最长有效括号

难度困难784

给定一个只包含 '('')' 的字符串,找出最长的包含有效括号的子串的长度。

示例 1:

1
2
3
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

1
2
3
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

通过次数74,856

提交次数233,569

题解见注释:主要是要两两字符判断;

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
int longestValidParentheses(string s) {
//动态规划:dp[i]:对于(0-i)个字符组成的字串的最长有效括号字串长度;
//对于...............():
//dp[i]=dp[i-2]+2;
//对于...............)):
//dp[i-1]表示(0-i-1)个字符组成的字串的最长有效括号字串长度:....(.....)
//判断s[i-dp[i-1]-1],如果是(:
//dp=dp[i-1]+2+dp[i-dp[i-1]-2] (最后一个因为.....((.....))匹配那么这个模式之前的一个也可以加入合法套餐了;

int n=s.length();;
vector<int>dp(n+1,0);
if(n==0 || n==1){
return 0;
}
int maxn=0;
for(int i=1;i<n;++i){
if(s[i]==')'){
if(s[i-1]=='('){
if(i>=2){
dp[i]=dp[i-2]+2;
}else{
dp[i]=2;
}
}else{
if(i-dp[i-1]-1>=0&&s[i-dp[i-1]-1]=='('){
if(i-dp[i-1]-2>=0)
dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2];
else{
dp[i]=dp[i-1]+2;
}
}
}
}
maxn=max(maxn,dp[i]);
}
return maxn;

}
};