Leetcode - 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.

[balabala]  自己只想出来DP包装的枚举实现，妥妥地超时。网上搜到了巧妙的解答，好好吸其精华。

 

public class Solution {
    // method 4: O(n)
    // dp[i]: 包含s.charAt[i - 1]的最长有效括号串长度
    // 所有'('对应的dp[i] == 0
    // 位置i - 1处为')' 时，若前面有匹配的'(', 其位置记为leftPos,  
    // dp[i]=当下(...)长度 + leftPos前一个位置处的最长有效括号串长 
    public int longestValidParentheses(String s) {
        if (s == null || s.length() < 2)
            return 0;
        int N = s.length();
        int[] dp = new int[N + 1];
        LinkedList<Integer> stack = new LinkedList<Integer>();
        int max = 0;
        for (int i = 1; i <= N; i++) {
            char c = s.charAt(i - 1);
            if (c == '(') {
                stack.push(i);
            } else if (!stack.isEmpty()){
                int leftPos = stack.pop();
                dp[i] = i - leftPos + 1 + dp[leftPos - 1];
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
    // method 3: O(n)
    // dp[i]表示从索引i到结尾的字符串的前缀的最长有效括号对长度
    // http://www.cnblogs.com/huntfor/p/3886111.html
    // 计算方向：自右向左
    public int longestValidParentheses3(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        int[] dp = new int[n];
        dp[n - 1] = 0;
        int max = 0;
        for (int i = n - 2; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                int j = i + 1 + dp[i + 1]; //寻找最长有效前缀的后驱
                if (j < n && s.charAt(j) == ')') {
                    dp[i] = dp[i + 1] + 2;
                    if (j + 1 < n)
                        dp[i] += dp[j + 1];
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
    
    // method 2: O(n)
    // http://www.cnblogs.com/lichen782/p/leetcode_Longest_Valid_Parentheses.html
    // http://blog.csdn.net/worldwindjp/article/details/39460161
    // 实现中的last变量记录的是有效串开始位置的前面一个下标，
    // 也是最后一个无法匹配的')'的下标，每个无法匹配的')'是一组组有效串的分界点
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int max = 0;
        int last = -1; 
        LinkedList<Integer> stack = new LinkedList<Integer>();// 栈中元素是每个入栈'(' 的下标
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (stack.isEmpty()) {
                    last = i; // 遇到')'且无人匹配，更新last为当前下标
                } else {
                    stack.pop();
                    if (!stack.isEmpty()) {
                        max = Math.max(max, i - stack.peek());
                    } else {
                        max = Math.max(max, i - last);
                    }
                }
            }
        }
        return max;
    }
    // method 1 : 枚举，O(n^3), 超时
    // dp[i][j] : tells whether s.substring(i, j) is a valid parentheses string
    public int longestValidParentheses1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // 预处理 - 不顶用, 通过分析算法的时间复杂度可知是杯水车薪。
        StringBuilder sb = new StringBuilder(s);
        int beg = 0;
        int end = s.length() - 1;
        for (int i = beg; i <= end; i++) {
            if (s.charAt(i) == ')')
                beg++;
            else
                break;
        }
        
        for (int i = end; i >= beg; i--) {
            if (s.charAt(i) == '(')
                end--;
            else
                break;
        }
        s = s.substring(beg, end + 1);
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        // 长度为奇数的子串不可能平衡, 无需计算
        // for (int i = 0; i < n; i++) {
        //     for (int j = i; j < n; j += 2) {
        //         dp[i][j] = false;
        //     }
        // }
        // 判断所有长度为2的子串
        for (int i = 0; i < n - 1; i++) {
            dp[i][i + 1] = s.charAt(i) == '(' && s.charAt(i + 1) == ')';
        }
        // 从小到大依次判断其他长度的子串, O(n^3)
        for (int len = 4; len <= n; len += 2) { // O(n)
            for (int i = 0; i < n - len + 1; i++) { // O(n)
                int j = i + len - 1;
                dp[i][j] = s.charAt(i) == '(' && s.charAt(j) == ')' && dp[i + 1][j - 1];
                for (int k = i + 1; k < j - 1; k += 2) { // O(n)
                    dp[i][j] |= dp[i][k] && dp[k + 1][j];
                }
            }
        }
        // 逆推，找到最长平衡串
        for (int len = n; len >= 2; len -= 2) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                if (dp[i][j])
                    return len;
            }
        }
        return 0;
    }
}

 

评论

2 楼 likesky3 2015-04-22  

DP还是没有理解到家吧，我的观念是DP能通过存储中间过程减少计算量，没想到它在这题中却是最复杂的。做完题目一定要有分析时间复杂度的意识，这样可以及时转换思路。原来method1的思想是贪婪啊，我没有意识到，是不是贪婪通常比DP简单，但是不一定全局最优？

1 楼 qb_2008 2015-04-21  

我想问题在于这道题不是DP，因为哪个左括号和哪个右括号匹配是固定的，你可以用一个栈
模拟（method 2），也可以用一个贪婪（method 1)。这种匹配或贪婪写得好就是O(n)，
因为只需要找到每个右括号匹配的左括号。method 1 的时间复杂度是O(n3)，因为多了
Line 96和Line 100的两个循环。
如果开始能尝试几个简单的例子，就会发现匹配是固定的，避免用复杂度较高的DP。不过
DP确实很适合这类匹配情况，不管三七二十一，用上DP，都不会做错