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　O(N) Time + O(N) Space

此题有多种解法。DP只是其中一种。
只有在碰到)的时候才需要去计算当前配对括号长度。
状态方程的解释是：
如果在)之前的符号是(，那么最长的合法字符串长度就是(之前的合法长度＋２
如果之前的符号是), dp[i - 1]代表了如果i - 1结尾的合法的最长长度，那么如果在dp[i - 1]之前的那个字符是（，
当前的合法长度就可以等于dp[i - 1] + dp[i - dp[i - 1] - 2]　＋　２
由此可以写出状态方程。

C++

1

Java

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
public class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] dp = new int[s.length()];
        int res = 0;
        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;  // add () to dp[i - 2]
                } else if (s.charAt(i - 1) == ')') {
                    if (i - dp[i -1] >= 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(dp[i], res);
            }
        }
        return res;
    }
}