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.
https://oj.leetcode.com/problems/longest-valid-parentheses/
方案1：DP，dp[i]代表从索引i到末尾最长的有效括号组合的长度。
dp[s.length()-1]=0;从后向前逆向求解dp[i]，
- 如果s[i]=')'，则显然dp[i]=0;
- 如果s[i]='('，跳过dp[i+1]这段长度从j=i+1+dp[i+1]开始，如果j没越界并且s[j]=')'，正好和s[i]匹配，则dp[i]=dp[i+1]+2；另外此时可能j之后的也可以连上，所以，可能要加上dp[j+1];
- 注意max初始要为0，考虑长度为1的情况。
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() < 2)
return 0;
int max = 0;
int[] dp = new int[s.length()];
dp[s.length() - 1] = 0;
for (int i = s.length() - 2; i >= 0; i--) {
char ch = s.charAt(i);
if (ch == '(') {
int j = i + 1 + dp[i + 1];
if (j < s.length() && s.charAt(j) == ')') {
dp[i] = dp[i + 1] + 2;
if (j + 1 < s.length())
dp[i] += dp[j + 1];
}
}
max = Math.max(max, dp[i]);
}
return max;
}
public static void main(String[] args) {
System.out.println(new Solution().longestValidParentheses("(((()(()"));
}
}
方案2：stack，时空复杂度都是O(n)。依次遍历字符串中的字符。如果是'（'，压栈索引。如果是'）'，分情况讨论：
- 如果此时栈为空，表示前面没有需要匹配的或者前面已经计算完毕，'）'不可能作为新的计算开始点，所以更新start为'）'的索引+1.（start 表示当前能构成合法括号组合的起始处）
- 如果此时栈不空，则出栈，若此时栈为空，则表示当前匹配，更新结果为当前索引-start+1； 若此时不为空，则表示从此时栈顶元素下一位到当前索引是合法的，更新结果为当前索引-栈顶元素索引。
方案2：
import java.util.Stack;
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() < 2)
return 0;
Stack<Integer> stack = new Stack<Integer>();
int start = 0;
int max = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(')
stack.push(i);
else {
if (stack.isEmpty())
start = i + 1;
else {
stack.pop();
if (stack.isEmpty())
max = Math.max(max, i - start + 1);
else
max = Math.max(max, i - stack.peek());
}
}
}
return max;
}
public static void main(String[] args) {
System.out.println(new Solution().longestValidParentheses("()()()))(()))("));
}
}
方案3：
http://huntfor.iteye.com/blog/2081942
参考：
http://blog.csdn.net/abcbc/article/details/8826782
http://codeganker.blogspot.com/2014/03/longest-valid-parentheses-leetcode.html