题解 | 最长的括号子串

dp[i]以i下标字符结尾的最长有效字符串的长度。

列举可能出现的有效括号的情况：

• ()
• ...()
• ((...))
• ...((...))

import java.util.*;
public class Solution {
    public int longestValidParentheses (String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int n = s.length();
        // dp[i]表示以i结尾最长有效括号的长度
        int[] dp = new int[n];
        int maxLen = 0;
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == '(') {
                dp[i] = 0;
            } else if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    // ()的情况
                    dp[i] = 2;
                    // ...()的情况
                    if (i - 2 > 0) {
                        dp[i] = dp[i - 2] + 2;
                    }
                } else if (s.charAt(i - 1) == ')') {
                    // ((...))的情况
                    // i-dp[i-1]-1为外层括号的下标
                    if (dp[i - 1] > 0 && (i - dp[i - 1] - 1) >= 0 &&
                            s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = dp[i - 1] + 2;
                        if (i - dp[i - 1] - 2 > 0) {
                            // ...((...))的情况
                            dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2;
                        }
                    } else {
                        dp[i] = 0;
                    }
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}