题目描述
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"
解题思路
①栈
首先初始化在栈底压入-1，然后遍历字符串，当遇到'('时，直接将下标压栈，当遇到')'时，如果栈不为空就首先弹出一个元素，并把下标进栈，详细思路可看https://leetcode-cn.com/problems/longest-valid-parentheses/solution/shou-hua-tu-jie-zhan-de-xiang-xi-si-lu-by-hyj8/
class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """ stack = [] stack.append(-1) max_len = 0 for i in range(len(s)): if s[i] == "(": stack.append(i) continue stack.pop() if not stack: stack.append(i) else: max_len = max(max_len, i - stack[-1]) return max_len S = Solution() print(S.longestValidParentheses(")()())"))②动态规划
我们单单看「子串」的末位s[i]，它要么是左括号，要么是右括号：
1. s[i]是'('，左括号作为末尾字符，以它为结尾的子串不是有效括号子串——dp[i] = 0 2. s[i]是')'，我们考察前一个子问题的末尾：s[i-1]
1. s[i-1]是'('，它们俩结成一对( )，考察s[i-2]
1. s[i-2]不存在，这一对落单，有效长度为 2——dp[i] = 2 2. 存在，考虑它们俩的前面提供的有效长度 dp[i] = dp[i-2] + 2
2. s[i-1]是')'，即'))'形式，这就来到子问题了，以s[i-1]为结尾形成的最长有效长度为dp[i-1]，跨过这个长度（里面细节不用管，总之它最大能提供dp[i-1]长度），来看s[i-dp[i-1]-1]这个字符
1. s[i-dp[i-1]-1]不存在或为')'，s[i]找不到匹配，直接gg，dp[i] = 0 2. s[i-dp[i-1]-1]是'('，它和s[i]遥相呼应，有效长度 2 保底！加上跨过的dp[i-1]，再加上前方的dp[i-dp[i-1]-2]…等等…s[i-dp[i-1]-2]要存在才行！
1. s[i-dp[i-1]-2]存在，dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2 2. s[i-dp[i-1]-2]不存在，dp[i] = dp[i-1] + 2
详细思路可看https://leetcode-cn.com/problems/longest-valid-parentheses/solution/shou-hua-tu-jie-zhan-de-xiang-xi-si-lu-by-hyj8/
class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """ dp = [0] * len(s) maxlen = 0 for i in range(1, len(s)): if s[i] == ')': if s[i - 1] == '(': if i - 2 >= 0: dp[i] = dp[i - 2] + 2 else: dp[i] = 2 elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '(': if i - dp[i - 1] - 2 >= 0: dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2 else: dp[i] = dp[i - 1] + 2 maxlen = max(maxlen, dp[i]) return maxlen S = Solution() print(S.longestValidParentheses("(()))())("))
