32. 最长有效括号

Difficulty
Hard
Tags
动态规划
URL
https://leetcode-cn.com/problems/longest-valid-parentheses/
Star
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
提示：
  • 0 <= s.length <= 3 * 104
  • s[i] 为 '(' 或 ')'
通过次数206,762提交次数578,831

法 2 栈

思路
先给栈中放一个 -1
然后遇到 ( ，将该索引入栈
遇到 ）栈顶弹出来，如果此时为空，将当前索引入栈，如果不空，那就计算当前索引和栈顶值的差。
题解
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = []
        # 栈第表示开始的子串的前一个 下标
        stack.append(-1)
        res = 0
        for i in range(0, len(s)):
            if s[i] =="(":
                stack.append(i)
            else:
                stack.pop()
                # 栈第表示开始的子串的前一个 下标
                if len(stack) == 0:
                    stack.append(i)

                res = max(res, i - stack[-1])

        return res

法1 动态规划

思路
状态dp[i] 表示 以右括号 s[i] 结尾的最长有效括号。
目前还不知道数目类型的动态规划。。。
只检测右括号，当s[i] == ")时，可以划分为如下两种类型：
  1. 类型1
      2. notion imagenotion image
      此类型，s[i-1] == "(" ，正好凑成一对，所以dp[i] = dp[i-2] + 2
  1. 类型2：
      2. notion imagenotion image
      此时，向前找一个可以匹配的左括号，那么该左括号一定是跨越以s[i-1]结尾的最长串，所以j = i - dp[i-1] - 1。 再判断 s [j] == ”（“, 如果是，则 dp[i] = dp[j-1] + dp[i-1] + 2
题解
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if len(s) <= 1:
            return 0
        
        dp = [0 for _ in range(len(s))]
        for i in range(1, len(dp)):
            if s[i] == ")":
                if s[i-1] == "(":
                    # 处理边界情况
                    if i >= 2:
                        dp[i] = dp[i-2] + 2
                    else:
                        dp[i] += 2
                else:
                    j = i - dp[i-1] - 1
                    if j >= 0 and s[j] == "(":
                        # 处理边界情况
                        if j >= 1:
                            dp[i] = dp[j-1] + dp[i-1] + 2
                        elif j == 0:
                            dp[i] = dp[i-1] + 2

        return max(dp)
显然，是s前面加一个 “#”就可以避免边界条件
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        s = "#" + s
        dp = [0 for _ in range(len(s))]
        res = 0
        for i in range(1, len(s)):
            if s[i] == ")":
                # 前一个就是
                if s[i-1] == "(":
                    dp[i] = dp[i-2] + 2
                # 前一组！！
                else:
                    j = i - dp[i-1] - 1
                    if j > 0 and s[j] == "(":
                        dp[i] = dp[j-1] + dp[i-1] + 2

                res = max(res, dp[i])

        return res