思路1：这个序列问题，很容易联想到用动态规划的思路来解最长公共字符串的问题，区别在于，在求最长公共字符串的时候，子状态从两个相邻字符开始判断，如果这两个字符不相等，则包含这两个相邻字符的一定不是公共字符串。而对于本题，如果两个相邻的括号不匹配，比如两个都是'('、'('，这两个不匹配，但以这两个子串为基础的其他子串不一定无法组成有效的括号，比如连续四个括号分别为'( ( ) )'这样的形式，无法从之前计算的两个右括号不匹配的情况推出现在四个括号的匹配情况。那么问题来了，针对本题的最优子状态应该怎么去找呢？
通过分析：两个匹配的左右括号，一定是相邻最近的匹配对，也就是最里层的括号一定是优先匹配，然后在逐层向外匹配，比如上述的四个连续括号'( ( ) )'的情况，一定是中间两个先匹配，然后再匹配外层的两个。如果我们在匹配第一个'('的时候，已经提前知道第二个和第三个已经组合为一个有效括号的话，那第一个就可以直接去匹配第四个左括号了，这样的话，对于第一个右括号，最长匹配有效括号长度就是4。
也就是说，如果从左边第一个匹配的时候，提前知道他右侧的已经匹配匹配好的最大长度了，那么就可以跳过已经匹配完成的情况了，比如'( ( ( ) ) )'这个情况，在匹配第一个右括号的时候，已经知道中间的两个括号对的话，则直接跳过，去匹配第六个做括号，即可得出最长匹配有效括号长度是6。
我们可以尝试从字符串的末端先提前生成上述两个情况的字符串匹配的结果，首先建立一个与输入字符串等长的数组a，用于保存每个字符串位置能匹配到的最长的长度，比如对于'( ( ( ) ) )'当计算第一个右括号的时候，已经知道a[1]的值是4，也就是从这个位置向右移动四个位置，可以算作第二个字符的匹配，所以计算第一个右括号的话，直接去匹配第五个。这就是我们要设计的动态规划的子状态了。
这里还有一个问题，对于'( ( ( ) ) ) ( )'，当计算第一个的值时，如果跳过这个a[1]的值4的长度之后，顺利匹配到第五个字符，而且匹配成功了，但是第五个字符的后面的字符串依然是一个匹配完成的字符串，则还要加上这段长度，然后再算作第一个字符的整体长度
这就是完整的思路了。具体代码如下：
int longestValidParentheses(const char *s)
{
int n=strlen(s);
if(n == 0)
return 0;
int i,j;
int dp[n];
int max=0;
for(i=0;i<n;i++)
dp[i]=0;
for(i=n-2;i>=0;i--)
{
if(s[i]=='(')
{
j=i+1+dp[i+1];
if(j<n && s[j]==')')
{
dp[i]=dp[i+1]+2;
if(j+1<n)
dp[i]+=dp[j+1];
}
}
if(max<=dp[i])
max=dp[i];
}
return max;
}
思路2:在思路1中我们知道，在一个括号序列里，当遇到一个左括号')'时，需要找到其左侧与其最近的右括号'('，而不是最靠前的右括号'('，比如输入序列'( ( ) )'，很明显第一个')'找到的时候内部的右括号'('也就是第二个右括号'('，而第一个右括号'('，需要等待其右边没有待匹配的右括号'('时候才开始匹配，针对本例，也就是匹配完内部的括号对再匹配外侧的括号对。
那么，当我们遇到输入序列的时候，如果首先遇到一个右括号'('，
1、如果其第二个输入的是左括号')'，则直接完成匹配；
2、如果其第二个输入的依然是右括号'('时候呢？我们是不是就要把第一个输入的右括号'('挂起，等第二个输入的右括号'('匹配到后边的左括号了，再来匹配被挂起的第一个右括号'('。
遇到这样的情形，可以将遇到的右括号'('推入栈stack[]数组中，并记录stack[top]为输入序列的索引位置，每遇到一个左括号')'，则从栈中推出一个右括号'('。
现在问题来了，我们现在知道如何去找到两个匹配的括号了，那么，怎么来计算最长的有效括号呢，上一步，每一次匹配成功，我们可以获取到两个有效括号对的索引，我们可以新建一个与输入字符串等长的mark数组，每遇到一个匹配成功的括号对，就将两个索引标记下来。等循环遍历完成，统计mark数组的最长连续标记的长度即可。废话不说了，上代码。
int longestValidParentheses(char* s) {
int len=strlen(s);
if(len <= 1)
return 0;
int* mark=(int*)malloc(sizeof(int)*len);
for(int i=0;i < len;i++)
mark[i] = -1;
int* stack=(int*)malloc(sizeof(int)*len);
int top=0;
for(int i = 0; i < len; i++){
if(s[i]=='(')
stack[top++]=i;
else{
if(top!=0){
mark[stack[top-1]]=0;
mark[i]=0;
top--;
}
}
}
int count=0;
int newCount=0;
for(int i = 0; i < len;i++){
if(mark[i]!= -1)
newCount++;
else{
if(newCount>count){
count=newCount;
}
newCount=0;
}
}
if(newCount>count)count=newCount;
return count;
}
本系列文章，旨在打造LeetCode题目解题方法，帮助和引导同学们开阔学习算法思路，由于个人能力和精力的局限性，也会参考其他网站的代码和思路，如有侵权，请联系本人删除。
网友评论