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

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

簡單說一下題意：
給定一個只包含"("或")"的字符串，找到括號格式正確的最長子字符串的長度，比如輸入為"(()"時，輸出為2，輸入為")()())"輸出為4。

此問題肯定需要遍歷所有字符，遍歷到一個")"時盡量利用前面獲取到的信息進(jìn)行配對，如果前面有能夠匹配的到的"("，這里“能夠匹配的到的”的意思是離其最近的沒有配對的"("，那么根據(jù)前面的信息計(jì)算出當(dāng)前位置最長有效子字符串的長度。計(jì)算的方法是：

我們使用n表示索引(0開始)，f(n)表示n位置字符參與的能夠配對的子字符串長度，那么上一個沒有配對的'('的位置為n - f(n-1) -2：

IMG_20180621_171404.jpg

根據(jù)推導(dǎo)公式實(shí)現(xiàn)的代碼：

public class LongestValidParentheses {
    public static void main(String[] args) {
        System.out.println(new LongestValidParentheses()
                                   .longestValidParentheses2("()(())"));
    }

    int longestValidParentheses2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] lengthArr = new int[s.length()];

        int max = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')' && i - lengthArr[i - 1] - 1 >= 0 && s
                    .charAt(i - lengthArr[i - 1] - 1) == '(') {
                lengthArr[i] = lengthArr[i - 1] + 2 + (i - lengthArr[i - 1] -
                        2 > 0 ? lengthArr[i - lengthArr[i - 1] - 2] : 0);
            }
            max = Math.max(max, lengthArr[i]);
        }

        return max;
    }
}

看到有的解決方案是創(chuàng)建一個s.length()+1的數(shù)組，0位置為保留位置，這樣就不用判斷“i - lengthArr[i - 1] - 2 > 0”了。

現(xiàn)在貼上代碼：

public int longestValidParentheses(String s) {
    int n = s.length();
    int max = 0;
    int[] dp = new int[n+1];
    for(int i = 1; i <= n; i++){
        if(s.charAt(i-1) == ')' && i-dp[i-1]-2 >= 0 && s.charAt(i-dp[i-1]-2) == '('){
            dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2];
            max = Math.max(dp[i], max);
        }
    }
    return max;
}