【leetcode】 Longest Valid Parentheses

地址

https://leetcode.com/problems/longest-valid-parentheses/description/

题目

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

思路

DP 时间复杂度O(n)

dp[i]表示以i结尾的最长连续配对长度。$dp[i]=2+dp[i-1]+dp[i-2-dp[i-1]]$当且仅当s[i]==')'&&s[i-1-dp[i-1]]=='('时。

其他 时间复杂度O(n)

利用栈把匹配的括号全部标为1，然后扫一遍求连续1的最大长度。

代码

DP

class Solution {
public:
    int longestValidParentheses(string s) {
        int len=s.length(),ans=0,dp[100000];
        memset(dp,0,sizeof dp);
        for(int i=1;i<len;i++)
        if(s[i]==')'&&s[i-1-dp[i-1]]=='(')
        {
            if(i-1-dp[i-1]-1>=0)
                dp[i]+=dp[i-1-dp[i-1]-1];
            ans=max(dp[i]+=2+dp[i-1],ans);
        }
        return ans;
    }
};

其他

class Solution {
public:
    int longestValidParentheses(string s) {
        int len=s.length(),ans=0,sum=0,sk[100000],top=0,ff[100000];
        memset(ff,0,sizeof ff);
        memset(sk,0,sizeof sk);
        for(int i=0;i<len;i++)
        if(s[i]=='(')
            sk[top++]=i;
        else if(!top)
            top=0;
        else
            ff[sk[--top]]=ff[i]=1;
        for(int i=0;i<len;i++)
        if(ff[i])
            ans=max(ans,++sum);
        else
            sum=0;
        return ans;
    }
};