LeetCode Python - 32.最长有效括号

题目

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = “”
输出：0

提示：

0 <= s.length <= 3 * 10⁴
s[i] 为 ‘(’ 或 ‘)’

答案

方法一：动态规划

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        f = [0] * (n + 1)
        for i, c in enumerate(s, 1):
            if c == ")":
                if i > 1 and s[i - 2] == "(":
                    f[i] = f[i - 2] + 2
                else:
                    j = i - f[i - 1] - 1
                    if j and s[j - 1] == "(":
                        f[i] = f[i - 1] + 2 + f[j - 1]
        return max(f)

方法二：使用堆栈

维护一个堆栈来存储左括号的索引。使用值 -1 初始化堆栈的底部元素，以便于计算有效括号的长度。
遍历字符串的每个元素：

如果字符是左括号，则将字符的索引推到堆栈上。
如果字符是右括号，请从堆栈中弹出一个元素，表示我们找到了一对有效的括号。
如果堆栈为空，则表示我们找不到与右括号匹配的左括号。在这种情况下，请将字符的索引作为新的起点推送。
如果堆栈不为空，请计算有效括号的长度并更新它。

总结：

该算法的关键是维护一个堆栈来存储左括号的索引，然后通过推送和弹出元素来更新括号的有效子字符串的长度。

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = [-1]
        ans = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    ans = max(ans, i - stack[-1])
        return ans