给一个一堆括号的字符串，然后返回最长的合法的括号的长度。关于括号的问题，我们在 20 题和 22 题也讨论过。

解法一 暴力解法

列举所有的字符串，然后判断每个字符串是不是符合。当然这里可以做个优化就是，因为合法字符串一定是偶数个，所以可以只列举偶数长度的字符串。列举从 0 开始的，长度是 2、4、6 ……的字符串，列举下标从 1 开始的，长度是 2、4、6 ……的字符串，然后循环下去。当然判断字符串是否符合，利用栈来实现，在之前已经讨论过了。

publicbooleanisValid(Strings) {
Stack<Character>stack=newStack<Character>();
for (inti=0; i<s.length(); i++) {
if (s.charAt(i) =='(') {
stack.push('(');
        } elseif (!stack.empty() &&stack.peek() =='(') {
stack.pop();
        } else {
returnfalse;
        }
    }
returnstack.empty();
}
publicintlongestValidParentheses(Strings) {
intmaxlen=0;
for (inti=0; i<s.length(); i++) {
for (intj=i+2; j<=s.length(); j+=2) {
if (isValid(s.substring(i, j))) {
maxlen=Math.max(maxlen, j-i);
            }
        }
    }
returnmaxlen;
}

时间复杂度: 列举字符串是 O（n²），判断是否是合法序列是 O（n），所以总共是 O（n³）。

空间复杂度：O（n），每次判断的时候，栈的大小。

这个算法，leetCode 会报时间超时。

解法二 暴力破解优化

解法一中，我们会做很多重复的判断，例如类似于这样的，（）（）（），从下标 0 开始，我们先判断长度为 2 的是否是合法序列。然后再判断长度是 4 的字符串是否符合，但会从下标 0 开始判断。判断长度为 6 的字符串的时候，依旧从 0 开始，但其实之前已经确认前 4 个已经组成了合法序列，所以我们其实从下标 4 开始判断就可以了。

基于此，我们可以换一个思路，我们判断从每个位置开始的最长合法子串是多长即可。而判断是否是合法子串，我们不用栈，而是用一个变量记录当前的括号情况，遇到左括号加 1，遇到右括号减 1，如果变成 0 ，我们就更新下最长合法子串。

publicintlongestValidParentheses(Strings) {
intcount=0;
intmax=0;
for (inti=0; i<s.length(); i++) {
count=0;
for (intj=i; j<s.length(); j++) {
if (s.charAt(j) =='(') {
count++;
            } else {
count--;
            }
//count < 0 说明右括号多了，此时无论后边是什么，一定是非法字符串了，所以可以提前结束循环if (count<0) {
break;
            }
//当前是合法序列，更新最长长度if (count==0) {
if (j-i+1>max) {
max=j-i+1;
                }
            }
        }
    }
returnmax;
}

时间复杂度：O（n²）。

空间复杂度：O（1）。

解法三 动态规划

首先定义动态规划的数组代表什么

dp [ i ] 代表以下标 i 结尾的合法序列的最长长度，例如下图

下标 1 结尾的最长合法字符串长度是 2，下标 3 结尾的最长字符串是 str [ 0 , 3 ]，长度是 4 。

我们来分析下 dp 的规律。

首先我们初始化所有的 dp 都等于零。

以左括号结尾的字符串一定是非法序列，所以 dp 是零，不用更改。

以右括号结尾的字符串分两种情况。

• 右括号前边是 ( ，类似于 ……（）。
  dp [ i ] = dp [ i - 2] + 2 （前一个合法序列的长度，加上当前新增的长度 2）
  类似于上图中 index = 3 的时候的情况。
  dp [ 3 ] = dp [ 3 - 2 ] + 2 = dp [ 1 ] + 2 = 2 + 2 = 4
  
• 右括号前边是 )，类似于 ……））。
  此时我们需要判断 i - dp[i - 1] - 1 （前一个合法序列的前边一个位置） 是不是左括号。
  例如上图的 index = 7 的时候，此时 index - 1 也是右括号，我们需要知道 i - dp[i - 1] - 1 = 7 - dp [ 6 ] - 1 = 4 位置的括号的情况。
  而刚好 index = 4 的位置是左括号，此时 dp [ i ] = dp [ i - 1 ] + dp [ i - dp [ i - 1] - 2 ] + 2 （当前位置的前一个合法序列的长度，加上匹配的左括号前边的合法序列的长度，加上新增的长度 2），也就是 dp [ 7 ] = dp [ 7 - 1 ] + dp [ 7 - dp [ 7 - 1] - 2 ] + 2 = dp [ 6 ] + dp [7 - 2 - 2] + 2 = 2 + 4 + 2 = 8。
  如果 index = 4 不是左括号，那么此时位置 7 的右括号没有匹配的左括号，所以 dp [ 7 ] = 0 ，不需要更新。
  

上边的分析可以结合图看一下，可以更好的理解，下边看下代码.

publicintlongestValidParentheses(Strings) {
intmaxans=0;
intdp[] =newint[s.length()];
for (inti=1; i<s.length(); i++) {
if (s.charAt(i) ==')') {
//右括号前边是左括号if (s.charAt(i-1) =='(') {
dp[i] = (i>=2?dp[i-2] : 0) +2;
//右括号前边是右括号，并且除去前边的合法序列的前边是左括号            } elseif (i-dp[i-1] >0&&s.charAt(i-dp[i-1] -1) =='(') {
dp[i] =dp[i-1] + ((i-dp[i-1]) >=2?dp[i-dp[i-1] -2] : 0) +2;
            }
maxans=Math.max(maxans, dp[i]);
        }
    }
returnmaxans;
}

时间复杂度：遍历了一次，O（n）。

空间复杂度：O（n）。

总

这几种算法，暴力破解和动态规划我觉得想的话，还是能分析出来的话，最后两种算法感觉是去挖掘题的本质得到的算法，普适性不是很强。但最后一种算法，从左到右，从右到左，是真的强。