# 32. Longest Valid Parentheses 最长有效括号

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.

Difficulty: Hard

### 解法1

``````class Solution {
public:
int longestValidParentheses(string s) {
int res = 0,start = 0;
stack<int> m;
for (int i=0;i<s.size();i++)
{
if (s[i]=='(')
m.push(i);
else if (s[i]==')')
{
if (m.empty()) start=i+1;
else
{
m.pop();
res = m.empty()?max(res,i-start+1):max(res,i-m.top());
}
}
}
return res;
}
};
``````

### 解法2

DP的思路如下:

``````if s[i]=='(',longest[i]=0,因为'('不可能为合法括号串
else if s[i]==')'
if  s[i-1]=='(', longest[i] = longest[i-2]+2
else if s[i-1]==')' && a[i-longest[i-1]-1]=='(', longest[i] = longest[i-1]+2+longest[i-longest[i-1]-2]
//比如输入"()(())",longest array [0,2,0,0,2,0],longest[5] = longest[4] + 2 + longest[1] = 6;
``````
``````class Solution {
public:
int longestValidParentheses(string s) {
if (s.length()<=1) return 0;
int curMax = 0;
vector<int> longest(s.size(),0);
for (int i=1;i<s.length();i++)
{
if (s[i]==')')
{
if (s[i-1]=='(')
{
longest[i] = (i-2)>=0?longest[i-2]+2:2;
curMax = max(longest[i],curMax);
}
else //s[i-1]==')'
{
if (i-longest[i-1]-1>=0&&s[i-longest[i-1]-1]=='(')
{
longest[i] = longest[i-1]+2+((i-longest[i-1]-2>=0)?longest[i-longest[i-1]-2]:0);
curMax = max(curMax,longest[i]);
}
}
}
}
return curMax;
}
};
``````

comments powered by Disqus