32. 最长有效括号

  |   0 评论   |   0 浏览

来源力扣(LeetCode)
难度:困难

题目描述
给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。

示例 1

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

示例 2

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

题解

方法一:暴力解法(超出时间限制了)
检查所有以左括号为起点,以右括号终止的子串是否有效,并记录有效子串的长度,从而找出最长有效子串的长度。

 1class Solution {
 2    public int longestValidParentheses(String s) {
 3        int ans = 0;
 4        if (s == null || s.length() == 0) {
 5            return ans;
 6        }
 7
 8        for (int i = 0; i < s.length() - ans; i++) {
 9            if (s.charAt(i) == ')') {
10                continue;
11            }
12            for (int j = i + 1; j < s.length(); j++) {
13                if (s.charAt(j) == '(') {
14                    continue;
15                }
16                if (isValid(s, i, j)) {
17                    ans = Math.max(ans, j - i + 1);
18                }
19            }
20        }
21
22        return ans;
23    }
24
25    /**
26     * 判断 s 中指定的的子串是否有效
27     * @param s 字符串
28     * @param start 子串起始位置
29     * @param end 子串终止位置
30     * @return 子串有效返回 true,无效返回 false
31     */
32    private boolean isValid(String s, int start, int end) {
33        int len = end - start + 1;
34        if (len % 2 == 1) {
35            return false;
36        }
37
38        int cnt = 0;
39        for (int i = start; i <= end; i++) {
40            if (s.charAt(i) == '(') {
41                cnt++;
42            } else if (cnt<=0) {
43                return false;
44            } else {
45                cnt--;
46            }
47        }
48
49        return cnt==0;
50    }
51}

方法二:使用栈
在有效的字符串中,连续的几个左括号必定会紧跟着同样数量的右括号,比如:"(())()"
从左向右扫描字符串,若遇到左括号则把它的下标压入栈,若遇到右括号则将栈顶元素弹出,此时当前元素和出栈元素之间的子串肯定是有效子串。

 1class Solution {
 2    public int longestValidParentheses(String s) {
 3        int ans = 0;
 4        LinkedList<Integer> stack = new LinkedList<>();
 5        stack.push(-1);
 6        for (int i = 0; i < s.length(); i++) {
 7            if (s.charAt(i) == '(') {
 8                stack.push(i);
 9            } else {
10                stack.pop();
11                if (stack.isEmpty()) {
12                    stack.push(i);
13                } else {
14                    ans = Math.max(ans, i - stack.peek());
15                }
16            }
17        }
18        return ans;
19    }
20}

*方法三:动态规划?
使用dp[i]表示以第 i 个字符结尾的有效子串最大长度。
s[i] == '(',则dp[i] = 0,因为有效子串肯定以右括号结尾。
s[i] == ')',则存在下面两种情况:

  • s[i-1] == '(',则dp[i] = dp[i-2] + 2
  • s[i-1] == ')',且s[(i - dp[i - 1] - 1)] == '(',则dp[i] = dp[i-1] + 2 + dp[i - dp[i - 1] - 2]
 1class Solution {
 2    public int longestValidParentheses(String s) {
 3        int ans = 0;
 4
 5        s = " " + s;
 6        int[] dp = new int[s.length()];
 7        for (int i = 2; i < s.length(); i++) {
 8            if (s.charAt(i) == ')') {
 9                if (s.charAt(i - 1) == '(') {
10                    dp[i] = dp[i - 2] + 2;
11                } else if (s.charAt(i - dp[i - 1] - 1) == '(') {
12                    dp[i] = dp[i-1] + 2 + dp[i - dp[i - 1] - 2];
13                }
14                ans = Math.max(ans, dp[i]);
15            }
16        }
17        
18        return ans;
19    }
20}

方法四
声明两个变量来记录左右括号的数量。
从左向右扫描字符串,从遇到的第一个左括号m开始计数,当左右括号数量相等时,则这个子串肯定是有效的,记录该子串的长度。
当右括号数量大于左括号数量时,说明之前的子串是以m为起点的最大子串,然后将两个变量重置为零,在剩余的字符串中重复之前的步骤。
仅仅从左向右扫描字符串,会漏掉一种情况,就是扫描的时候左括号的数量始终大于右括号的数量,例如:(()(),因此还需要从右向左扫描。

 1class Solution {
 2    public int longestValidParentheses(String s) {
 3        int ans = 0;
 4        int ltCount = 0;
 5        int rtCount = 0;
 6
 7        // 从左向右
 8        for (int i = 0; i < s.length(); i++) {
 9            if (s.charAt(i) == '(') {
10                ltCount++;
11            } else {
12                rtCount++;
13            }
14
15            if (ltCount == rtCount) {
16                ans = Math.max(ans, ltCount+rtCount);
17            } else if (rtCount > ltCount) {
18                ltCount = 0;
19                rtCount = 0;
20            }
21        }
22
23        ltCount = 0;
24        rtCount = 0;
25        // 从右向左
26        for (int i = s.length() - 1; i >= 0 ; i--) {
27            if (s.charAt(i) == ')') {
28                rtCount++;
29            } else {
30                ltCount++;
31            }
32
33            if (ltCount == rtCount) {
34                ans = Math.max(ans, ltCount + rtCount);
35            } else if (ltCount > rtCount) {
36                ltCount = 0;
37                rtCount = 0;
38            }
39        }
40
41        return ans;
42    }
43}