IT源码网

最长有效括号讲解

developer 2020年10月27日 编程语言 534 0

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

示例 1:

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

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

解:这道题和那道最长回文串有点像,状态转移方程为

f(n)=f(n-2)+2 if(s[n]==')'&&s[n-1]=='(')  //这种情况说明是像()()这种连续的

f(n)=f(n-f(n-1)-2)+2 if(s[n]==')'&&s[n-f(n-1)-1]=='(')

下面上代码

class Solution { 
public: 
        int longestValidParentheses(string s) { 
        if(s.size()<2) 
        { 
            return 0; 
        } 
        int i_max=INT_MIN; 
        vector<int> dp(s.size(),0); 
        for(int i=1;i<s.size();i++) 
        { 
            if(s[i]==')') 
            { 
                //如果前一个为左,则匹配左括号 
                if(s[i-1]=='(') 
                { 
                    dp[i]=(i>=2?dp[i-2]:0)+2;\ 
                } 
                //匹配前面括号嵌套的情况 
                //i-dp[i-1]>0防止单独的右括号情况出现 
                //i-dp[i-1]-1为i-1匹配的前一个字符, 
                else if(i-dp[i-1]>0&&s[i-dp[i-1]-1]=='(') 
                { 
                    //再减1为左括号左边的连续匹配个数 
                    dp[i]=dp[i-1]+((i-dp[i-1]-1)>=1?dp[i-dp[i-1]-1-1]:0)+2; 
                } 
            } 
            i_max=max(i_max,dp[i]); 
        }         
        return i_max; 
    } 
};

 

发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

c++引用和运算符重载思考讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。