LeetCode32-最长有效括号

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/longest-valid-parentheses/

中文链接：https://leetcode-cn.com/problems/longest-valid-parentheses/

题目详述

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

1
2
3
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

1
2
3
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

题目详解

  • 动态规划。
  • f(i) 表示当前以 ) 结尾的匹配括号长度。
  • 当前 s[i] == '('，则 f(i) = 0。
  • 当前 s[i] == ')'，则
    • 如果 s[i - 1] == '('，则 f[i] = f[i - 2] + 2，形如 ...()。
    • 如果 s[i - f[i - 1] - 1] == '('，则 f[i] = f[i - f[i - 1] - 2] + f[i - 1] + 2，形如 ...(...)。
  • 结果为状态数组最大值。
  • 时间复杂度为 O(n)，空间复杂度为 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00032 {

    public int longestValidParentheses(String s) {
        int res = 0;
        int[] f = new int[s.length()];
        for (int i = 1; i < s.length(); ++i) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    f[i] = (i >= 2 ? f[i - 2] : 0) + 2;
                } else if (i - f[i - 1] > 0 && s.charAt(i - f[i - 1] - 1) == '(') {
                    f[i] = f[i - 1] + ((i - f[i - 1] >= 2 ? f[i - f[i - 1] - 2] : 0) + 2);
                }
                res = Math.max(res, f[i]);
            }
        }
        return res;
    }
}
  • 可以换一种思路，运用两个变量 left 和 right 进行计数。
  • 从左往右遍历字符串，碰到 (，left 自增；碰到 )，right 自增。
    • 如果 left > right，存在匹配的可能性，继续向前遍历。
    • 如果 left == right，说明括号匹配成功，此时长度为 left + right，更新结果。
    • 如果 left < right，说明这一段不能匹配成功，重置 left = right = 0。
  • 为了得到正确结果，还需要从右往左遍历一次。
    • 如果 left > right，说明这一段不能匹配成功，重置 left = right = 0。
    • 如果 left == right，说明括号匹配成功，此时长度为 left + right，更新结果。
    • 如果 left < right，存在匹配的可能性，继续向前遍历。
  • 时间复杂度为 O(n)，空间复杂度为 O(1)。
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
public class LeetCode_00032 {

    public int longestValidParentheses(String s) {
        int res = 0;
        for (int i = 0, left = 0, right = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                ++left;
            } else {
                ++right;
            }
            if (left == right) {
                res = Math.max(res, left << 1);
            } else if (left < right) {
                left = 0;
                right = 0;
            }
        }
        for (int i = s.length() - 1, left = 0, right = 0; i >= 0; --i) {
            if (s.charAt(i) == '(') {
                ++left;
            } else {
                ++right;
            }
            if (left == right) {
                res = Math.max(res, left << 1);
            } else if (left > right) {
                left = 0;
                right = 0;
            }
        }
        return res;
    }
}