题目描述
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
思路解析
只有出现右括号，才会统计有效长度
这个问题可以通过动态规划解决。我们定义一个 dp 数组，dp[i]表示以第i个结尾能够产生的最长括号匹配长度。我们将 dp 数组全部初始化为 0 。现在，很明显有效的子字符串一定以 ‘)’ 结尾。这进一步可以得出结论：以 ( 结尾的子字符串对应的dp 数组位置上的值必定为 0 。所以说我们只需要更新)在dp 数组中对应位置的值。
为了求出dp 数组，我们每两个字符检查一次，如果满足如下条件
如果s[i] == “）”,s[i-1] == "(" 则，dp[i] = dp[i-2] + 2
如果s[i] == ")"， s[i-1] == ")",判断s[i - dp[i-1] - 1] == "(",则，dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]
但是需要判断i - dp[i-1] - 1、i - dp[i-1] - 2以及i-2是否存在，注意边界。
class Solution:
def longestValidParentheses(self, s):
if not s or len(s) == 0:
return 0
dp = [0] * len(s)
res = 0
for i in range(1, len(s)):
if s[i] == ")":
if s[i-1] == "(":
dp[i] = 2 + (dp[i-2] if i-2 >= 0 else 0)
elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == "(":
dp[i] = 2 + dp[i-1] + (dp[i-dp[i-1]-2] if i-dp[i-1]-2 >= 0 else 0)
res = max(res, dp[i])
return res
AC32
