32. Longest Valid Parentheses

发表于 | 分类于

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.

Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

解法1： DP

用一个array,dp[i]表示的是0 … i子串里lvp。首先如果要valid,那么最后一个字符一定是). 这就是说我们只需要在看到)的时候判断一下当前最长的子串。
那么可以得到如下的推算公式。
如果i字符是(，那么如果i-1是(,则代表有一个valid的子串，dp[i] = dp[i - 2] + 2
如果i字符是)，那么先要看i - 1位置的最长子串，然后看这个子串的前一个字符是否是(，如果是那么我们又凑满了一个valid的子串。
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int longestValidParentheses(String s) {
        int res = 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] && 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;
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

解法２: Stack

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
class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int start = -1;
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (!stack.isEmpty()) {
                    stack.pop();
                    if (stack.isEmpty()) {
                        res = Math.max(res, i - start);
                    } else {
                        res = Math.max(res, i - stack.peek());
                    }
                } else {
                    start = i;  // because if a string starts with ) it will never become valid
                }
            }
        }
        return res;
    }
}