32. 最长有效括号

English Version

题目描述

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

 

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

 

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 '(' 或 ')'

解法

方法一：动态规划

定义 dp[i] 表示以 s[i] 结尾的最长有效括号的长度，答案为 max(dp[i])。

dp[i] 的值有以下几种情况：

• 若 s[i] 为 (，那么 dp[i] = 0；
• 若 s[i] 为 )，且 s[i - 1] 为 (，那么 dp[i] = dp[i - 2] + 2；
• 若 s[i] 为 )，且 s[i - 1] 为 ) 且 s[i - dp[i - 1] - 1] 为 (，那么 dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]。

以上需要注意边界的判断处理。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 s 的长度。

Python3

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n < 2:
            return 0
        dp = [0] * n
        for i in range(1, n):
            if s[i] == ')':
                if s[i - 1] == '(':
                    dp[i] = 2 + (dp[i - 2] if i > 1 else 0)
                else:
                    j = i - dp[i - 1] - 1
                    if j >= 0 and s[j] == '(':
                        dp[i] = 2 + dp[i - 1] + (dp[j - 1] if j else 0)
        return max(dp)

Java

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        if (n < 2) {
            return 0;
        }
        char[] cs = s.toCharArray();
        int[] dp = new int[n];
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            if (cs[i] == ')') {
                if (cs[i - 1] == '(') {
                    dp[i] = 2 + (i > 1 ? dp[i - 2] : 0);
                } else {
                    int j = i - dp[i - 1] - 1;
                    if (j >= 0 && cs[j] == '(') {
                        dp[i] = 2 + dp[i - 1] + (j > 0 ? dp[j - 1] : 0);
                    }
                }
                ans = Math.max(ans, dp[i]);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        if (n < 2) return 0;
        vector<int> dp(n);
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = 2 + (i > 1 ? dp[i - 2] : 0);
                } else {
                    int j = i - dp[i - 1] - 1;
                    if (~j && s[j] == '(') {
                        dp[i] = 2 + dp[i - 1] + (j ? dp[j - 1] : 0);
                    }
                }
                ans = max(ans, dp[i]);
            }
        }
        return ans;
    }
};

Go

func longestValidParentheses(s string) int {
	n := len(s)
	if n < 2 {
		return 0
	}
	dp := make([]int, n)
	ans := 0
	for i := 1; i < n; i++ {
		if s[i] == ')' {
			if s[i-1] == '(' {
				dp[i] = 2
				if i > 1 {
					dp[i] += dp[i-2]
				}
			} else {
				j := i - dp[i-1] - 1
				if j >= 0 && s[j] == '(' {
					dp[i] = 2 + dp[i-1]
					if j > 0 {
						dp[i] += dp[j-1]
					}
				}
			}
			ans = max(ans, dp[i])
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

...