题目

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

示例 1:

输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"

解题思路

看了题解才想到的。。。但是感觉不是很难啊？为啥没想出来呢。。

栈版：用栈来判断是否能组成括号，但是记的个数不是括号的个数，而是当前元素和栈顶元素的下标差。如果碰到栈为空，当前元素是'('，栈顶元素是')'，都把当前元素入栈，其他时候则pop栈的元素

dp版： 只有当前位置是')'时可能组成新的括号，有2种可能：要么组成括号的是...()，要么组成括号的是...))。 对于前者，很简单就能写出转移方程：dp[i] = dp[i - 2] + 2； 对于后者，需要解决2个问题：

判断i-1的位置的)，有没有和它配对的(，如果有，有几个？去掉这些已经和它配对的括号后，再前1位的字符是否为(以便和当前这个)配对？

第一个问题用dp数组可以看到，也即dp[i - 1]是否为0，如果是0，说明没有和它配对的，如果不是0，那么dp[i - 1]就代表了有几个位置是已经配对好的。 对于第二个问题，其实只要用当前的下标，减去前面那些已经配对好的位置，就可以知道再前1位字符是什么了。 所以如果前面那个位置的字符为(，当前位置的dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2，等式的第一部分是前面那个能够配对的(再前1位已经配对的个数，第二部分是从和当前)配对的(开始向后，直到当前的)之间，已经配对的个数，最后1个2就是这俩配对的括号。

在实际代码的时候，需要额外处理一下输入字符串是()的情况，因为dp[i] = dp[i - 2] + 2，所以前置1个0即可，这样的话上面的下标做相应改动即可

代码

栈版：

class Solution: def longestValidParentheses(self, s: str) -> int: stack = [] cnt = 0 for index in range(len(s)): if (not stack) or s[index] == '(' or s[stack[-1]] == ')': stack.append(index) else: stack.pop() cnt = max(cnt, index - (stack[-1] if stack else -1)) return cnt

dp版：

class Solution: def longestValidParentheses(self, s: str) -> int: dp = [0, 0] cnt = 0 for index in range(1, len(s)): if s[index] == ')': if s[index - 1] + s[index] == '()': dp.append(dp[-2] + 2) elif index - dp[index] - 1 >= 0 and s[index - dp[index] - 1] == '(': dp.append(dp[index - dp[index] - 1] + dp[index] + 2) else: dp.append(0) else: dp.append(0) cnt = max(cnt, dp[-1]) return cnt