Zeki's Blog
0%

最长有效括号

Posted on

最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

1
2
3
4
5
6
7
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

思路：

  1. 暴力

    遍历数组，以每一个索引开始寻找最长的合法括号串。然后找出最大的长度返回

  2. dp

    定义：dp[i]：以索引i结尾的元素的最长合法括号串

    存在以下递推关系：

    dp[i] = dp[i-2] + 2 // 如果str[i] 与 str[i - 1] 为：()

    dp[i] = dp[i-1] + 2 + dp[i - 2 - dp[i-1]] // 如果str[i] = ')' && str[i - dp[i-1] - 1] = '('

代码：

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
class Solution {
    public int longestValidParentheses(String s) {
        char sc[] = s.toCharArray();
        int length = sc.length;
        int dp[] = new int[length];
        int max = 0;
        for(int i=1;i<length;i++){
            // 状况1
            if(sc[i]==')'&&sc[i-1]=='('){
                int pos = i-2;
                if(pos<0){
                    dp[i] = 2;
                } else{
                    // 更新dp
                    dp[i] = dp[pos] + 2;
                }
            }
            // 状况2
            if(sc[i]==')'&&sc[i-1]==')'){
                int pos = i-dp[i-1]-1;
                if(pos>=0&&sc[pos]=='('){
                    // 更新dp
                    dp[i] = dp[i-1] + 2;
                    // 加前面的 重要：((()))(()), 如果此时索引为9，dp[i-1] = 2 (), 前面需要加的就是((()))
                    if(dp[i-1]!=0&&pos-1>=0){
                        dp[i] += dp[pos-1];
                    }
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}