【leetcode】Longest Valid Parentheses

Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

 
设dp[i]表示从s[i]开始(包括s[i]),到达s[n-1]时,最长的有效括号对的长度。
 
如果s[i]=='('
我们需要检查j=dp[i+1]+i+1对应的s[j]位置的括号是否为")",如果s[j]为')'则说明又组成了一对括号
故此时dp[i]=dp[i+1]+2
于此同时,我们还需要继续考虑dp[j+1]的值,如果j+1没有超出范围,则dp[i]=dp[i+1]+2+dp[j+1]
 
其他情况dp[i]=0;
 
 class Solution {
public:
int longestValidParentheses(string s) {
int n=s.length();
if(n==) return ; int *dp=new int[n];
dp[n-]=; int result=;
for(int i=n-;i>=;i--)
{
if(s[i]=='(')
{
int j=dp[i+]+i+; if(s[j]==')')
{
dp[i]=dp[i+]+;
if(j<n-) dp[i]+=dp[j+];
}
else
{
dp[i]=;
} if(dp[i]>result)
{
result=dp[i];
}
}
else
{
dp[i]=;
}
}
delete [] dp;
return result;
}
};
上一篇:csdn博客刷点击率代码


下一篇:纯CSS3实现3D动画导航,html5 webRTC技术实现免费网页电话拨打