最长有效括号

问题简述

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

思路 1：动态规划（推荐）

• dp[i] = 2 + dp[i−1] + dp[i−dp[i−1]−2]，说明见下图：

  

  时刻注意数组下标的有效性，即 i-1 >= 0 and i−dp[i−1]−2 >= 0

Python（迭代，推荐）

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s: return 0

        dp = [0] * len(s)
        for i in range(len(s)):
            if i >= 1 and i - dp[i-1] - 1 >= 0 and s[i - dp[i-1] - 1] == '(' and s[i] == ')':
                dp[i] = 2 + dp[i-1] + dp[i - dp[i-1] - 2]
        
        return max(dp)

Python（递归）

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        
        from functools import lru_cache

        ret = [0]

        @lru_cache(maxsize=None)
        def dfs(i):  # s[i] 结尾的最长有效括号
            if i <= 0: return 0

            if i - dfs(i - 1) - 1 >= 0 and s[i - dfs(i - 1) - 1] == '(' and s[i] == ')':
                r = 2 + dfs(i - 1) + dfs(i - dfs(i - 1) - 2)
                ret[0] = max(ret[0], r)
                return r
            else:
                return 0
        
        dfs(len(s) - 1)
        return ret[0]

思路 2：栈

• 技巧性很强的方法，临场可能很难写出来，详见：最长有效括号（方法 2） - 力扣官方题解