leetcode32 最长有效括号

题目

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

分析

动态规划问题。记dp[i]为遍历到第i位置的时候，以下标i结尾时的最长有效括号数。当遍历到“(”时，以其结尾，一定不为有效括号，所以为0。当以")"结尾时的状态转移方程为：

• 当最后两个为"()"时，dp[i]=dp[i−2]+2
• 当最后两个为"))"，且dp[i - dp[i - 1] - 1]位置为"("能与i位置匹配时，dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2。

代码

class Solution {
public:
    int longestValidParentheses(string s) {
        
        int len = s.size(), res = 0;
        vector<int> dp(len, 0);

        for (int i = 1; i < len; 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;
                }

                res = max(res, dp[i]);
            }
        }

        return res;
    }
};