给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 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; } };
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/17571.html