【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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}
};

其他

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}
};