1、题目描述

https://leetcode-cn.com/problems/longest-valid-parentheses/

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

2、代码详解

情况2 s[i]==  ′  )  ′   

这时，需要看其前面对元素来判断是否有有效括号对。

情况2.1

情况2.2 ： 特殊case )()(()))

class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """ n = len(s) if n == 0: return 0 # dp[i] 表示以 i 结尾的最长有效括号 dp = [0] * n res = 0 for i in range(n): # 1:当 s[i] 为 (,dp[i] 必然等于 0，因为不可能组成有效的括号 # 2：那么 s[i] 为 ) if i > 0 and s[i] == ")": # 2.1 当 s[i-1] 为 ( if s[i - 1] == "(": dp[i] = dp[i - 2] + 2 # 2.2 当 s[i-1] 为 ) 并且 s[i-dp[i-1] - 1] 为 ( elif s[i - 1] == ")" and i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == "(": dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2] # 测试用例 )()(())) if dp[i] > res: res = dp[i] return res s = ')()(()))' # 6 S = Solution() print(S.longestValidParentheses(s))

https://leetcode-cn.com/problems/longest-valid-parentheses/solution/dong-tai-gui-hua-si-lu-xiang-jie-c-by-zhanganan042/