题解 | #最长的括号子串#

动态规划，dp[ i ]表示以下标i结尾的字符串的最长有效括号的长度。最长有效括号的长度：就是尾端的右括号’)’和前面的左括号’(’括起来的部分的长度。于是对于第i个位置，如果s[ i ] == ’(’，则前面没有与之相匹配的左括号dp[ i ] = 0.如果s[ i ] == ’)’，分为两种情况，当s[ i - 1 ] == ’(’时，dp[ i ] = dp[ i - 2 ] + 2；当s[ i - 1 ] == ’)’时，也就是尾端两个右括号’))’的情况，此时把i位置的右括号看成是内层的匹配，把i - 1位置的右括号看成是内层的匹配，于是，与i右括号匹配的左括号的位置是i - dp[ i - 1 ] - 1，当s[ i - dp[ i - 1 ] - 1 ] == ’(’时，dp[ i ] = dp[ i - 1 ] + 2；否则dp[ i ]为i - dp[ i - 1 ] - 1到i这一段加上i - dp[ i - 1 ] - 1之前的部分：dp[ i ] = dp[ i ] + dp[ i - dp[ i - 1 ] - 2 ].

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    int longestValidParentheses(string s) {
        int len = 0, n = s.length();
        vector<int> dp(n, 0);
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                len = max(len, dp[i]);
            }
        }
        return len;
    }
};