最长有效括号力扣--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]24,此时漏加了前半部分的只统计了后半部分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 [] dpnew int[s.length()]; int result0; for(int i0;is.length();i){ if(i0 s.charAt(i))){ if(s.charAt(i-1)(){ dp[i](i-20 ? dp[i-2]2:2); }else if(s.charAt(i-1)) i-dp[i-1]-10 s.charAt(i-dp[i-1]-1)(){ dp[i]dp[i-1]2(i-dp[i-1]-20?dp[i-dp[i-1]-2]:0); } } resultMath.max(result,dp[i]); } return result; } }python语言class Solution: def longestValidParentheses(self, s: str) - int: nlen(s) dp[0]*n res0 for i in range(n): if i0 and s[i]): if s[i-1](: dp[i]dp[i-2]2 elif s[i-1]) and i-dp[i-1]-10 and s[i-dp[i-1]-1](: dp[i]dp[i-1]2dp[i-dp[i-1]-2] if dp[i]res: resdp[i] return res