最长有效括号力扣--32
目录
题目
分析
补充示例
推导
java语言
python语言
题目
给你一个只包含'('和')'的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如"(()())"。
示例 1：
输入：s = "(()"输出：2解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"输出：4解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""输出：0
提示：
0 <= s.length <= 3 * 104s[i]为'('或')'
分析
这里为了方便理解，多补充几个示例：
补充示例
示例1：字符串：()(())
索引：0 1 2 3 4 5
最终最长有效括号是：6
示例2：输入："((()))"
整个串都有效
结果：6
推导
dp[i]表示以i结尾的最长有效括号长度
有两种情况：
如果s[i]为）当s[i-1]为（那么dp[i]=dp[i-2]+2,这里需要额外判断一下i-2是否大于0，不然报错。
另一种情况是比如示例2：是嵌套的，当i为4时候，i-1也为)，但是其实他是一对一对对应的，那么就判断i-dp[i-1]-1(i减去已有连续字串的长度再减1)是否大于0，且他是否为（,如果满足以上两个条件，那么递推公式为dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]；刚开始不明白为什么还要加do[i-dp[i-1]-2],给出示例1，当遍历到5的时候，如果没有后半部分，那么dp[5]=dp[4]+2=4,此时漏加了前半部分的（），只统计了后半部分，dp[i-dp[i-1]-2]=dp[5-dp[4]-2]=dp[5-2-2]=dp[1]=2，加上以后才为最终结果
java语言
class Solution { public int longestValidParentheses(String s) { int [] dp=new int[s.length()]; int result=0; for(int i=0;i<s.length();i++){ if(i>0 && s.charAt(i)==')'){ if(s.charAt(i-1)=='('){ dp[i]=(i-2>=0 ? dp[i-2]+2:2); }else if(s.charAt(i-1)==')' && i-dp[i-1]-1>=0 && s.charAt(i-dp[i-1]-1)=='('){ dp[i]=dp[i-1]+2+(i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0); } } result=Math.max(result,dp[i]); } return result; } }python语言
class Solution: def longestValidParentheses(self, s: str) -> int: n=len(s) dp=[0]*n res=0 for i in range(n): if i>0 and s[i]==")": if s[i-1]=="(": dp[i]=dp[i-2]+2 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