目录

0032:最长有效括号(★★)

力扣第 32 题

题目

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

示例 1:

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

示例 2:

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

示例 3:

输入:s = ""
输出:0

提示:

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

相似问题:

分析

类似 1249 ,可以先模拟匹配得到有效括号的位置,找出最长连续段即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        A = [0]*len(s)
        sk = []
        for i,c in enumerate(s):
            if c=='(':
                sk.append(i)
            elif sk:
                A[i] = A[sk.pop()] = 1
        return max([len(list(g)) for c,g in groupby(A) if c==1], default=0)

30 ms

*附加

还可以用 dp 解决:

  • 令 dp[i] 代表下标 i 结尾的最长有效长度,
    • 假如 i 是右括号,对应的左括号下标为 j,dp[i]=j-i+1+dp[j-1]
    • 其它情况下,dp[i]=0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        dp = [0]*len(s)
        sk = []
        for i,c in enumerate(s):
            if c=='(':
                sk.append(i)
            elif sk:
                j = sk.pop()
                dp[i] = i-j+1+(dp[j-1] if j else 0)
        return max(dp,default=0)

48 ms