题目描述

给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 “(()())”。

示例：
输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”

题目分析

动态规划。
设 dp[i] 表示以位置 i 结尾的有效子串最大长度，则当 s[i] 为 ‘)’ 时：
– s[i – 1] 为 ‘(‘ ，例如 “()()” ，dp[i] = dp[i – 2] + 2
– s[i – 1] 为 ‘)’ 且 i – 1 处为有效子串 且 子串前为 ‘(‘，例如”()(())“，dp[i] = dp[i – 1] + 2 + dp[子串前2位]

在 dp 中取最大值即可.
时间复杂度 O(n)

Java

public int longestValidParentheses(String s) {
    int[] dp = new int[s.length()];
    int ans = 0;
    for (int i = 1; i < s.length(); i++) {
        char ch = s.charAt(i);
        char pre = s.charAt(i - 1);
        if (ch == ')') {
            if (pre == '(') {
                dp[i] = i >= 2 ? dp[i - 2] + 2 : 2;
            } else {
                int before = i - dp[i - 1] - 1;
                if (before >= 0 && s.charAt(before) == '(') {
                    dp[i] = dp[i - 1] + 2;
                    if (before >= 1) {
                        dp[i] += dp[before - 1];
                    }
                }
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

Kotlin

fun longestValidParentheses(s: String): Int {
    val dp = IntArray(s.length)
    var ans = 0
    for (i in s.indices) {
        if (s[i] == ')' && i - 1 >= 0) {
            if (s[i - 1] == '(') {
                dp[i] = if (i - 2 >= 0) dp[i - 2] + 2 else 2
            } else if (dp[i - 1] > 0) {
                val before = i - dp[i - 1] - 1
                if (before >= 0 && s[before] == '(') {
                    dp[i] = dp[i - 1] + 2
                    if (before >= 1) {
                        dp[i] += dp[before - 1]
                    }
                }
            }
        }
        ans = max(ans, dp[i])
    }
    return ans
}