Longest Valid Parentheses
Source
- leetcode: 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
length = 2.
Another example is ")()())", where the longest valid parentheses substring
is "()()", which has length = 4.
题解
To detect a valid parentheses substring, we use a stack to maintain left parentheses: Each time when hitting a '(', push its index to the stack. Each time when hitting a ')', If the stack is not empty, i.e. there is a matching '(' for it, pop the match out of the stack. At this time, we know it is an end of a valid parentheses substring. Calculate the length of the current substring and compare it with the longest we've got. If the stack is empty, there is no matching '(' for it. Move on to next character. The tricky part is how to calculate the length of the "current substring". E.g. to differentiate "()(()" and "(()()", or "())()" and ")()()".
We need to track the position where the current substring started. For case one, "()(()" and "(()()", the extra '(' must be in stack. So, after pop up a matching '(', the next top of the stack is right before the start position of the current substring. For case two, "())()" and ")()()", we need to keep track of the last invalid ')'.
Java
public class Solution {
public int longestValidParentheses(String s) {
int maxLen = 0, last = -1;
Stack<Integer> lefts = new Stack<Integer>();
for (int i=0; i < s.length(); ++i) {
if (s.charAt(i)=='(') {
lefts.push(i);
}
else {
if (lefts.isEmpty()) {
// no matching left
last = i;
}
else {
// find a matching pair
lefts.pop();
if (lefts.isEmpty()) {
maxLen = Math.max(maxLen, i-last);
}
else {
maxLen = Math.max(maxLen, i-lefts.peek());
}
}
}
}
return maxLen;
}
}