1、题目描述：

2、题解：

方法1：栈
思路：

遍历：
栈顶保存当前合法字符串的首个字符的位置下标
遇到”(“就把下标入栈
遇到”)“就把栈顶元素出栈（完成匹配）
这时候有两种情况：
栈空，就把当前的下标入栈
栈不空，就更新最长长度：当前位置减去栈顶存的位置，就得到当前合法括号的长度

class Solution:def longestValidParentheses(self, s: str) -> int:#栈maxlen = 0stack = [-1]for i in range(len(s)):c = s[i]if c == "(":stack.append(i)continuestack.pop()if len(stack) == 0:stack.append(i)else:maxlen = max(maxlen,i - stack[- 1])return maxlen

方法2：动态规划

动态规划问题，弄清楚三点：
1、重复子问题；
2、最优子结构；
3、无后效性。

动态规划：
1、状态定义；
2、状态转移方程；
3、初始化；base case
4、输出；
5、思考状态压缩。
可以用递归去求，但是会存在重叠子问题，加个备忘录可以解决重复问题。

状态定义：
dp[i]表示以下标i为字符结尾的最长有效括号的长度
状态转移方程：

思考两种情况：
以'('为结尾的字符不可能构成合法字符
如果s[i] == ')'：1)如果"...()",也就是s[i-1] == '(':	dp[i]=dp[i-2]+2.		解释：也就是以i为结尾的字符最长有效括号的长度就为i-2处的最长有效括号的长度+22)如果"...((...))",也就是s[i-1]==')',并且s[i-dp[i-1]-1] == '(':	dp[i]=（dp[i-1]+2）+dp[i-dp[i-1]-2]		解释：如果"...))"，我们分两个，一个是第一个省略号之前和之后的情况。具体解释是：我们看以i-1结尾的有效括号的长度的前面（也即是看第一个省略号后面的字符）的字符是否是"("，如果是，那么该括号正好和s[i]位置的')'相匹配那么dp[i-1]+2，还有要加上这个有效括号dp[i-dp[i-1]-2]之前的情况(在此是看一个省略号处的最后一个字符为结尾的字符串的有效括号的个数。

注意处理一些边界情况
dp[i-2]
dp[i-dp[i-1]-1]

例如下图：
对于i=4来说，s[4] == “)”， s[3]== “)”,属于上面的第二种情况,那么我们需要先算出以s[3]为结尾的有效括号的个数dp[i-1]也就是dp[3]=2，然后看以s[3]为结尾的有效字符串之前的字符，即s[i-dp[3]-1]的括号是否满足要求，因为s[i-dp[3]-1]== “(”，与s[4] = ')'相匹配，那么就是dp[3]+2，然后再加上以这段有效括号之前的字符为结尾的有效括号的长度dp[i-dp[3]-2]

class Solution:def longestValidParentheses(self, s: str) -> int:#动态规划n = len(s)if n == 0:return 0dp = [0] * nfor i in range(1,len(s)):if s[i] == ')':if s[i - 1] == '(':dp[i] = dp[i - 2] + 2 if i > 2 else 2elif 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 i - dp[i - 1] - 2 >= 0 else dp[i-1]+2return max(dp)

3、复杂度分析：

方法1：
时间复杂度：O(N)
空间复杂度：O(N)
方法2：
时间复杂度：O(N)
空间复杂度：O(N)