32. Longest Valid Parentheses

,

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
31
32
33
34
class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> leftBracketIndexStack = new Stack<>();

        int maxLength = 0;
        int startIndex = 0; // 指向首个左括号
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftBracketIndexStack.push(i);
            } else {
                // c == ')'
                if (leftBracketIndexStack.isEmpty()) {
                    // 无可匹配的左括号，括号对只能从下一个字符开始
                    startIndex = i + 1;
                } else {
                    // 注意此处弹出的左括号索引不会被使用，因为以当前右括号结尾的最长有效括号子串不一定左侧为弹出的这个左括号
                    // eg: ()()
                    leftBracketIndexStack.pop();

                    if (leftBracketIndexStack.isEmpty()) {
                        // 栈中无左括号了，使用 startIndex 作为起点才是最长的有效括号，eg: ()()，因为只要字符串有效，就不会重置 startIndex
                        maxLength = Math.max(maxLength, i - startIndex + 1);
                    } else {
                        // 栈中存在左括号，使用栈中左括号的下一个索引作为起点，eg: ((()，此时不能使用 startIndex
                        maxLength = Math.max(maxLength, i - leftBracketIndexStack.peek());
                    }
                }
            }
        }

        return maxLength;
    }
}

DP(TLE)

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
class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();

        int maxLength = 0;

        // 定义 dp[i][j] 为 s[i, j] 是否为有效的括号子串
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            char l = s.charAt(i);
            for (int j = i + 1; j < n; j++) {
                char r = s.charAt(j);

                if (l == '(' && r == ')') {
                    if (j == i + 1) {
                        // ()
                        dp[i][j] = true;
                    } else {
                        // (())
                        dp[i][j] = dp[i + 1][j - 1];
                    }

                    // ()()
                    for (int leftEndIndex = i + 1; leftEndIndex < j - 1 && !dp[i][j]; leftEndIndex++) {
                        dp[i][j] = dp[i][leftEndIndex] && dp[leftEndIndex + 1][j];
                    }

                    if (dp[i][j]) {
                        maxLength = Math.max(maxLength, j - i + 1);
                    }
                }
            }
        }

        return maxLength;
    }
}

DP

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
class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int maxLength = 0;

        // 定义 dp[i] 为 s 前 i 个字符组成的字符串的最长有效括号子串的长度
        int[] dp = new int[n + 1];

        for (int i = 1; i <= s.length(); i++) {
            char c = s.charAt(i - 1);
            if (c == ')') {
                // 只能以 ')' 结尾时可能组成有效括号子串

                if (i - 2 >= 0) {
                    char prev = s.charAt(i - 2);
                    if (prev == '(') {
                        // end with "()"
                        dp[i] = dp[i - 2] + 2;
                    } else {
                        // prev == ')', end with "))"
                        int subStrLength = dp[i - 1];
                        if (subStrLength > 0) {
                            int leftmostIndex = i - 1 - subStrLength - 1;
                            if (leftmostIndex >= 0 && s.charAt(leftmostIndex) == '(') {
                                dp[i] = dp[leftmostIndex] + 1 + dp[i - 1] + 1;
                            }
                        }
                    }

                    maxLength = Math.max(maxLength, dp[i]);
                }
            }
        }

        return maxLength;
    }
}

References

32. Longest Valid Parentheses