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.
分析
无
使用栈
// Longest Valid Parenthese
// 使用栈，时间复杂度O(n)，空间复杂度O(n)
public class Solution {
public int longestValidParentheses(String s) {
// the position of the last ')'
int maxLen = 0, last = -1;
// keep track of the positions of non-matching '('s
Stack<Integer> lefts = new Stack<>();
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) =='(') {
lefts.push(i);
} else {
if (lefts.empty()) {
// no matching left
last = i;
} else {
// find a matching pair
lefts.pop();
if (lefts.empty()) {
maxLen = Math.max(maxLen, i-last);
} else {
maxLen = Math.max(maxLen, i-lefts.peek());
}
}
}
}
return maxLen;
}
}
Dynamic Programming, One Pass
// Longest Valid Parenthese
// 两遍扫描，时间复杂度O(n)，空间复杂度O(1)
// @author 曹鹏(http://weibo.com/cpcs)
class Solution {
public int longestValidParentheses(final String s) {
int result = 0, depth = 0, start = -1;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '(') {
++depth;
} else {
--depth;
if (depth < 0) {
start = i;
depth = 0;
} else if (depth == 0) {
result = Math.max(result, i - start);
}
}
}
depth = 0;
start = s.length();
for (int i = s.length() - 1; i >= 0; --i) {
if (s.charAt(i) == ')') {
++depth;
} else {
--depth;
if (depth < 0) {
start = i;
depth = 0;
} else if (depth == 0) {
result = Math.max(result, start - i);
}
}
}
return result;
}
}两遍扫描
// Longest Valid Parenthese
// 两遍扫描，时间复杂度O(n)，空间复杂度O(1)
// @author 曹鹏(http://weibo.com/cpcs)
class Solution {
public int longestValidParentheses(final String s) {
int result = 0, depth = 0, start = -1;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '(') {
++depth;
} else {
--depth;
if (depth < 0) {
start = i;
depth = 0;
} else if (depth == 0) {
result = Math.max(result, i - start);
}
}
}
depth = 0;
start = s.length();
for (int i = s.length() - 1; i >= 0; --i) {
if (s.charAt(i) == ')') {
++depth;
} else {
--depth;
if (depth < 0) {
start = i;
depth = 0;
} else if (depth == 0) {
result = Math.max(result, start - i);
}
}
}
return result;
}
}