LeetCode-100题(Hot) 32. 最长有效括号 [Java实现] [极速]

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

示例 1:

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


动态规划yyds

设 dp[s.length()] 中 dp[i] 为 [0, i] 处最长有效括号长度,经分析输入可分为以下几种情况(前后/中间夹杂着 '(' 或 ')' )

  1.  "()()...()()"
  2. "((...()...))"
  3. "()()...((...()...))"

那么我们对于任何一个合法开头(开头为'(' )的括号字符串都有:

    public int longestValidParentheses(String s) {
        char[] chars = s.toCharArray();
        if (chars.length < 2) return 0;

        int result = 0;
        int[] dp = new int[chars.length];
        for (int i = 1; i < chars.length; ++ i) {
            if (chars[i] == 41) {
                if (chars[i-1] == 40) {
                    // 三目处理 '()..()..()' 的情况
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
                } else if (i-dp[i-1] > 0 && chars[i - dp[i-1] - 1] == 40) {
                    // 三目处理 '()(..(..)..)' 的情况
                    dp[i] = dp[i-1] + (i-dp[i-1] >= 2 ? dp[i - dp[i-1] - 2] : 0) + 2;
                }
                if (dp[i] > result) {
                    result = dp[i];
                }
            }
        }
        return result;
    }