题目
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
1
2
3
| 输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
|
示例 2:
1
2
3
| 输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
|
题目分析
暴力法
在这种方法中，我们考虑给定字符串中每个可能的非空偶数长度子字符串，并检查它是否是有效的括号字符串。为了检查有效性，我们使用堆栈方法。
每当我们遇到一个$\text{‘(‘} $，我们就把它推到堆栈上。对于遇到的每个$\text{‘)’} $，我们都会从堆栈中弹出一个$\text{‘(‘} $。如果$\text{‘(‘} $在堆栈上不可随时弹出，或者如果堆栈在处理完完整的子字符串后包含一些元素，括号中的子字符串无效。这样，我们对每一个可能的子串重复这个过程，并继续存储迄今为止找到的最长有效字符串的长度。
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 class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push('(');
} else if (!stack.empty() && stack.peek() == '(') {
stack.pop();
} else {
return false;
}
}
return stack.empty();
}
public int longestValidParentheses(String s) {
int maxlen = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i + 2; j <= s.length(); j+=2) {
if (isValid(s.substring(i, j))) {
maxlen = Math.max(maxlen, j - i);
}
}
}
return maxlen;
}
}
|
复杂度分析：
- 时间复杂度：$O(n^3)$ , 从长度为 $n$ 的字符串产生可能的子串需要$O(n^2)$ , 检查长度有效性需要 $O(n)$
- 空间复杂度：$O(n)$ , 栈的长度为 $n$
动态规划
这个问题可以通过使用动态规划来解决。我们使用 $\text{dp}$ 数组，其中 $\text{dp}$ 的第 $i$ 元素表示以 $i$ 索引结尾的最长有效子字符串的长度。我们用0初始化完整的 $\text{dp}$ 数组。现在，很明显，有效的子字符串必须以 $\text{‘)’} $ 结尾。这进一步导致以 $\text{‘(‘} $ 结尾的子字符串在其对应的 $\text{dp}$ 索引处总是包含’ 0 ‘。因此，我们仅在遇到 $\text{‘)’} $ 时更新 $\text{dp}$ 数组。
要填充 $\text{dp}$ 数组，我们将每两个连续字符检查一次字符串，如果
$\text{s}[i]=’)’ $ 、 $\text{s}[i - 1] = \text{‘(’}$, 例如这种字符串 “……()” $\Rightarrow$
$\text{dp}[i]=\text{dp}[i-2]+2$
我们这样做是因为结尾 “()” 部分无论如何都是有效的子串，并导致前一个有效子串的长度增加2。
$\text{s}[i] = \text{‘)’}$、 $\text{s}[i - 1] = \text{‘)’}$ 例如这种字符串
如果 $\text{s}[i - \text{dp}[i - 1] - 1] = \text{‘(’}$ 那么
$\text{dp}[i]=\text{dp}[i-1]+\text{dp}[i-\text{dp}[i-1]-2]+2$
$\text{dp}[i]$ 表示以当前位置为终点的最长长度，则只能在 ）处更新，
如果 $\text{s}[i - \text{dp}[i - 1] - 1] = \text{‘(’}$，则说明当前位置可以和 $i-1-\text{dp}[i-1]$ 位置匹配，$\text{dp}[i]=\text{dp}[i-1]+2$
然后还要加上匹配位置之前的最长长度 $\text{dp}[i]+=\text{dp}[i-\text{dp}[i]]$
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Solution {
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;
}
}
|
利用栈
我们可以在扫描给定字符串时使用堆栈来检查到目前为止扫描的字符串是否有效，以及最长有效字符串的长度，而不是查找每个可能的字符串并检查其有效性。为了做到这一点，我们首先将-1 -1推到堆栈上。
对于遇到的每一个 $\text{‘(‘}$ ，我们将其索引推送到堆栈上。
对于遇到的每一个$\text{‘)’} $，我们弹出最顶端的元素，并从堆栈的顶端元素中减去当前元素的索引，这将给出当前遇到的有效括号字符串的长度。如果弹出元素时，堆栈变空，我们将当前元素的索引推到堆栈上。这样，我们继续计算有效子字符串的长度，并在末尾返回最长有效字符串的长度。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class Solution {
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
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
| public class Solution {
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;
}
}
|
更多动态规划问题
更多动态规划问题关注标签：动态规划