leetcode 力扣 32 最长有效括号 python

目录

1. 解答
   1. DP
   2. 两次遍历
   3. 栈

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”
示例 2:

输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

DP

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

两次遍历

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        def fun(s, t):
            left = 0
            right = 0
            max_length = 0
            for ch in s:
                if ch == t: left += 1
                else: right += 1
                if left == right: max_length = max(max_length, left<<1)
                elif right > left:
                    left = 0
                    right = 0
            return max_length
        return max(fun(s, '('), fun(s[::-1], ')'))

栈

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        l = [-1]
        max_length = 0
        cur = 0
        for i, ch in enumerate(s):
            if ch == '(':
                l.append(i)
            else:
                l.pop()
                if not l:
                    l.append(i)
                else:
                    max_length = max(max_length, i - l[-1])
        return max_length