来源Leetcode第32题最长有效括号
给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 2:
输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”
Wrong Answer
一开始看到这题，我是用的栈写的，通过判断栈顶元素和入栈元素是否匹配，如果匹配则长度+2，不匹配则重新初始化长度，然而这样会有个问题，对于形如”()(()”这样的组合，我的输出是4，然而预期应该是2，其实还是因为算法不够完善。
思考了一番，既然如此，那我就对每一个可能的子串组合进行统计，记录所有子串里最长的有效括号，然而这在第227/230个算例时，发生了TLE,T T，先附上没有AC的代码吧：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| public int isLegal(String s) {
if (s.length() == 0)
return 0;
int index = 0;
char[] stack = new char[s.length()];
for (int i = 0; i < s.length(); i++) {
switch (s.charAt(i)) {
case '(':
stack[index++] = s.charAt(i);
continue;
case ')':
if (index == 0 || stack[index - 1] != '(')
{
return 0;
}
if(stack[index - 1] == '('){
index--;
continue;
}
}
}
return index == 0 ? 1 : 0;
}
public int longestValidParentheses(String s) {
int maxlength = 0;
for(int i = 0 ;i < s.length();i++){
for(int j = i + 2;j<=s.length();j+=2){
if(isLegal(s.substring(i,j)) == 1){
maxlength = Math.max(maxlength , j - i);
}
}
}
return maxlength;
}
|
栈
在查看题解时，我看到了一篇也是用栈写的，不过答主是用了下标入栈，通过判断出栈元素之间的距离来判断最长的有效括号长度。
我们扫描到左括号，就将当前位置入栈。
扫描到右括号，就将栈顶出栈（代表栈顶的左括号匹配到了右括号），然后分两种情况。
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int longestValidParentheses(String s) {
int maxans = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}
|
依次比对
此外，我们可以判断从每个位置开始的最长合法子串是多长即可。而判断是否是合法子串，我们不用栈，而是用一个变量记录当前的括号情况，遇到左括号加 1，遇到右括号减 1，如果变成 0 ，我们就更新下最长合法子串。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public int longestValidParentheses(String s) {
int count = 0;
int max = 0;
for (int i = 0; i < s.length(); i++) {
count = 0;
for (int j = i; j < s.length(); j++) {
if (s.charAt(j) == '(') {
count++;
} else {
count--;
}
if (count < 0) {
break;
}
if (count == 0) {
if (j - i + 1 > max) {
max = j - i + 1;
}
}
}
}
return max;
}
|
动态规划
接下来就是官方题解里提到的动态规划
dp[i] 代表以下标 i 结尾的合法序列的最长长度，
我们来分析下 dp 的规律。
首先我们初始化所有的 dp 都等于零。
以左括号结尾的字符串一定是非法序列，所以 dp 是零，不用更改。
以右括号结尾的字符串分两种情况。
- 右括号前边是 ( ，类似于 ……（）。
dp[i] = dp[i-2] + 2 （前一个合法序列的长度，加上当前新增的长度 2）
- 右括号前边是 )，类似于 ……））。
此时我们需要判断 i-dp[i-1]-1 （前一个合法序列的前边一个位置） 是不是左括号。
如果是左括号，此时dp[i] = dp[i-1]+dp[i-dp[i -1]-2]+2 （当前位置的前一个合法序列的长度，加上匹配的左括号前边的合法序列的长度，加上新增的长度 2）
如果不是左括号，那么此时位置 的右括号没有匹配的左括号，所以 dp[i] = 0 ，不需要更新。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int longestValidParentheses(String s) {
int maxans = 0;
int dp[] = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (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]);
}
}
return maxans;
}
|
两次遍历
当然还有一种很神奇的解法：
从左到右扫描，用两个变量 left 和 right 保存的当前的左括号和右括号的个数，都初始化为 0 。
- 如果左括号个数等于右括号个数了，那么就更新合法序列的最长长度。
- 如果左括号个数大于右括号个数了，那么就接着向右边扫描。
- 如果左括号数目小于右括号个数了，那么后边无论是什么，此时都不可能是合法序列了，此时 left 和 right 归 0，然后接着扫描。
从左到右扫描完毕后，同样的方法从右到左再来一次，因为类似这样的情况 ( ( ( ) ) ，如果从左到右扫描到最后，left = 3，right = 2，期间不会出现 left == right。但是如果从右向左扫描，扫描到倒数第二个位置的时候，就会出现 left = 2，right = 2 ，就会得到一种合法序列。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public int longestValidParentheses(String s) {
int left = 0, right = 0, maxlength = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * right);
} else if (right >= left) {
left = right = 0;
}
}
left = right = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * left);
} else if (left >= right) {
left = right = 0;
}
}
return maxlength;
}
|