0032：最长有效括号（★★）

2015-02-01 约 339 字预计阅读 1 分钟次阅读

力扣第 32 题

题目

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

0 <= s.length <= 3 * 10⁴
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

目录

0032：最长有效括号（★★）

题目

分析

解答

*附加