Question:
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.
Anwser 1 :
class Solution {
public:
int longestValidParentheses(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
stack<int> S;
for(int i = 0; i < s.size(); ++i){ // "("
if (s[i] == '(') {
S.push(i);
} else if (!S.empty()){ //')'
s[i] = 'k';
s[S.top()] = 'k';
S.pop();
}
}
// example: "(()" = "(kk"; "(()()" = "(kkkk"
int maxLength = 0;
int length = 0;
for(int i = 0; i < s.size(); ++i){ // count of "k"
if (s[i] =='k'){
++length;
if (maxLength < length) {
maxLength = length;
}
} else {
length = 0;
}
}
return maxLength;
}
};
Anwser 2 :
class Solution {
public:
struct node {
char c;
int idx;
node() {}
node(char _c, int _idx): c(_c), idx(_idx) {}
};
int longestValidParentheses(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
stack<node> st;
st.push(node(')', -1));
int res = 0;
for (int i = 0; i < s.size(); ++i)
{
char c = s[i];
if (c == '(') {
st.push(node(c, i));
} else {
node top = st.top();
if (top.c == '(') {
st.pop();
res = max(res, i - st.top().idx); // count or length
} else {
st.push(node(c, i));
}
}
}
return res;
}
};