032.Longest Valid Parentheses
in

032.Longest Valid Parentheses

?> with 0 comment

题目链接

题目

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

分析

栈实现

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if len(s) == 0:
            return 0
        res = 0
        stack = [-1]
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                # 里边只有"("
                stack.pop()
                if len(stack):
                    # 上一个多余括号,或者从头开始算
                    res = max(res, i - stack[-1])
                else:
                    # 如果stack是空,且输入')'
                    stack.append(i)
        return res

动态规划

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        res = 0
        s = ')' + s
        dp = [0 for _ in s]
        for i in range(1, len(s)):
            if s[i] == ')':
                if s[i - 1 - dp[i-1]] == '(':
                    dp[i] = dp[i-1] + 2
                # 比如(()())
                dp[i] += dp[i-dp[i]]
            res = max(res, dp[i])
        return res
Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号·苏公网安备 32059002001895号