最长有效括号
熊孩纸
阅读:716
2020-10-27 22:26:51
评论:0
给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
解:这道题和那道最长回文串有点像,状态转移方程为
f(n)=f(n-2)+2 if(s[n]==')'&&s[n-1]=='(') //这种情况说明是像()()这种连续的
f(n)=f(n-f(n-1)-2)+2 if(s[n]==')'&&s[n-f(n-1)-1]=='(')
下面上代码
class Solution { public: int longestValidParentheses(string s) { if(s.size()<2) { return 0; } int i_max=INT_MIN; vector<int> dp(s.size(),0); for(int i=1;i<s.size();i++) { if(s[i]==')') { //如果前一个为左,则匹配左括号 if(s[i-1]=='(') { dp[i]=(i>=2?dp[i-2]:0)+2;\ } //匹配前面括号嵌套的情况 //i-dp[i-1]>0防止单独的右括号情况出现 //i-dp[i-1]-1为i-1匹配的前一个字符, else if(i-dp[i-1]>0&&s[i-dp[i-1]-1]=='(') { //再减1为左括号左边的连续匹配个数 dp[i]=dp[i-1]+((i-dp[i-1]-1)>=1?dp[i-dp[i-1]-1-1]:0)+2; } } i_max=max(i_max,dp[i]); } return i_max; } };
声明
1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。