【LeetCode】 最长有效括号（python）

题目描述

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

示例 1:

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

题目解析
本题可以通过动态规划方法进行求解，dp[i]为当前i位置有效括号长度。
1、循环遍历s，当遇到右括号时，尝试向前匹配左括号：

			if s[i] == ')':
                pre = i - dp[i - 1] - 1

2、如果是左括号，则更新匹配后的长度：

				if pre >= 0 and s[pre] == '(':
                    dp[i] = dp[i - 1] + 2

3、处理独立的括号对的情形 类似()()、()(())

					 if pre>0:
                        dp[i] += dp[pre-1]

完整代码

'''
动态规划
'''
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        length = len(s)
        if not s:
            return 0
        dp = [0] * length
        for i in range(1, length):
            if s[i] == ')':
                pre = i - dp[i - 1] - 1
                if pre >= 0 and s[pre] == '(':
                    dp[i] = dp[i - 1] + 2
                    if pre > 0:
                        dp[i] += dp[pre - 1]
        return max(dp)