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