32. Longest Valid Parentheses (Hard)
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.
Solution 1: Stack 15ms
Time Complexity: $$O(n)$$
这道求最长有效括号比之前那道 Valid Parentheses 验证括号难度要大一些，这里我们还是借助栈来求解，需要定义个start变量来记录合法括号串的起始位置，我们遍历字符串，如果遇到左括号，则将当前下标压入栈，如果遇到右括号，如果当前栈为空，则将下一个坐标位置记录到start，如果栈不为空，则将栈顶元素取出，此时若栈为空，则更新结果和i - start + 1中的较大值，否则更新结果和i - 栈顶元素中的较大值，代码如下：
stack为空，说明到当前')'为止所有的括号被匹配，需要更新一下result; 不为空说明有左括号还未被匹配，要比较当前这个右括号与上一个左括号的
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> lefts; // store the idx of '('
int res = 0, start = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') lefts.push(i);
else {
if (lefts.empty()) start = i+1;
else {
lefts.pop();
res = lefts.empty() ? max(res, i-start+1):max(res, i-lefts.top());
}
}
}
return res;
}
};
Solution 2: Stack 12ms
The workflow of the solution is as below.
Scan the string from beginning to end.
If current character is '(', push its index to the stack.
If current character is ')' and the character at the index of the top of stack is '(', we just find a matching pair so pop from the stack. Otherwise, we push the index of ')' to the stack.
After the scan is done, the stack will only contain the indices of characters which cannot be matched. Then let's use the opposite side - substring between adjacent indices should be valid parentheses.
If the stack is empty, the whole input string is valid. Otherwise, we can scan the stack to get longest valid substring as described in step 3.
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
stack<int> st;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') st.push(i);
else {
if (st.empty()) st.push(i);
else if (s[st.top()] == '(') st.pop();
else st.push(i);
}
}
// all pairs are matching;
if (st.empty()) return n;
int a = n, b = 0, res = 0;
while (!st.empty()) {
b = st.top(); st.pop();
res = max(res, a-b-1);
a = b;
}
return max(res, a);
}
};
Solution 3: DP
My solution uses DP. The main idea is as follows: I construct a array longest[], for any longest[i], it stores the longest length of valid parentheses which is end at i.
And the DP idea is :
If s[i] is '(', set longest[i] to 0,because any string end with '(' cannot be a valid one.
Else if s[i] is ')'
If s[i-1] is '(', longest[i] = longest[i-2] + 2
Else if s[i-1] is ')' and s[i-longest[i-1]-1] == '(', longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]
For example, input "()(())", at i = 5, longest array is [0,2,0,0,2,0], longest[5] = longest[4] + 2 + longest[1] = 6.
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{ // if s[i-1] == ')', combine the previous length.
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(longest[i],curMax);
}
}
}
//else if s[i] == '(', skip it, because longest[i] must be 0
}
return curMax;
}
version 2:
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] == ')' && 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(longest[i],curMax);
}
}
return curMax;
}