即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

[Leetcode]_32 Longest Valid Parentheses

编程语言 lx417147512 31℃ 0评论
本文目录
[隐藏]
/**
 *  Index: 32
 *  Title: Longest Valid Parentheses
 *  Author: ltree98
 **/

题意是求最长合法字符串。


只要中间不中断即可。


比如:


(())() 是合法的。


1.stack

通过栈来实现。


1. 先压入一个 -1,方便计算长度。


2. 从第一个字符开始,依次判断;如果当前的字符与栈顶字符可以构成合法括号对,就弹出栈顶字符,计算长度;否则压入栈。


3. 将最大值返回。

这个方法,关键之处就在于第一个压入的-1,通过这个可以计算出不中断合法串的长度。

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        stk.push(-1);
        int maxLen=0;
        for(int i = 0; i < s.length(); i++)
        {
            int t = stk.top();
            if(t != -1 && s[i] == ')' && s[t] == '(')
            {
                stk.pop();
                maxLen = max(maxLen, i-stk.top());
            }
            else
                stk.push(i);
        }
        return maxLen;
    }
};


2.dp

第二种方法是用动态规划来解。


从后向前遍历字符串。

dp[i] = 第i个字符开始到最后的最长匹配字符串的长度。

i = len-1 -> 0


s[i] 匹配 s[i+1+dp[i+1]] => dp[i] = dp[i+1]+2+dp[i+1+dp[i+1]]


s[i] 不匹配 s[i+1+dp[i+1]] => dp[i] = 0

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        int dp[100001];
        memset(dp, 0, sizeof(dp));

        int maxLen = 0;
        for(int i = n-2; i >= 0; i--)   {
            if(s[i] == '(') {
                int j = i+1 + dp[i+1];
                if(j < n && s[j] == ')')    {
                    dp[i] = dp[i+1]+2;
                    if(j + 1 < n)
                        dp[i] += dp[j+1];
                }
            }
            maxLen = max(dp[i], maxLen);
        }
        return maxLen;
    }
};

转载请注明:CodingBlog » [Leetcode]_32 Longest Valid Parentheses

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情