【LeetCode 32】最长有效括号

【题解】

设dp[i]表示以第i个字符结尾的最长有效括号的长度。
显然只要考虑s[i]==')'的情况
则如果s[i-1]=='(',则dp[i] = dp[i-2]+2;
如果s[i-1]==')',那么我们现在要在i前面去给s[i]==')'这个右括号去找左括号。
那么显然我们要先让s[i-1]这个右括号得到匹配。不然轮不到s[i].
所以我们先往前走dp[i-1]长度.
然后看看i-1-dp[i-1]是不是左括号(这时才能轮得上s[i],这里面其实还要求dp[i]真的是最长的有效括号长度才行,不然不能直接这样判断)
是的话我们就得到一个长度为dp[i-1]+2的有效序列了。
当然别忘了前面还有dp[i-1-dp[i-1]-1]要加上去因为也可能是合法的匹配序列。

【代码】

class Solution {

public:

    int longestValidParentheses(string s) {

        int dp[100000];

        memset(dp,0,sizeof(dp));

        int len = s.size();

        int ans = 0;

        for (int i = 0;i < len;i++){

            if (s[i]==')'){

                if (i-1>=0){

                    if (s[i-1]=='('){

                        if (i-2<0) dp[i] = 2;else

                        dp[i] = dp[i-2]+2;

                    }else{

                        //s[i-1]==')'

                        if (i-1-dp[i-1]>=0&& s[i-1-dp[i-1]]=='('){

                            dp[i] = dp[i-1]+2;

                            if (i-1-dp[i-1]-1>=0){

                                dp[i]+=dp[i-1-dp[i-1]-1];

                            }

                        }

                    }

                }

            }

            ans = max(ans,dp[i]);

        }

        return ans;

    }

};

巴特西

【LeetCode 32】最长有效括号

最新文章

热门文章