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.
SOLUTION 1:
1. 使用栈来保存‘(‘
2. tmp 表示当前计算的一套完整的括号集的长度。（完整的指的是消耗掉栈中所有的‘(‘）
3. sum 表示数个完整的括号集的总长。
例子：
// 有一套完整的括号集，可以加到前面的一整套括号集上
// () (()())
// 1 2 第二套括号集可以加过来
4. 不完整的括号集：
这种情况也是需要计算的。
// 也可能是一个未完成的括号集，比如：
// () (()() 在这里 ()() 是一个未完成的括号集，可以独立出来计算，作为
// 阶段性的结果
5. 栈为空时，出现一个‘)‘，可以将sum置0.
1 public class Solution { 2 public int longestValidParentheses(String s) { 3 if (s == null) { 4 return 0; 5 } 6 7 Stack<Integer> stk = new Stack<Integer>(); 8 int sum = 0; 9 int tmp = 0; 10 11 int max = 0; 12 13 for (int i = 0; i < s.length(); i++) { 14 char c = s.charAt(i); 15 16 if (c == ‘(‘) { 17 stk.push(i); 18 } else { 19 if (stk.isEmpty()) { 20 // 栈中没有‘(‘,出现‘)‘, 则必须重置计算 21 sum = 0; 22 continue; 23 } 24 25 // count the temporary lenght: 26 // like: (()()() 27 // tmp = 2. 28 tmp = i - stk.pop() + 1; 29 if (stk.isEmpty()) { 30 // 有一套完整的括号集，可以加到前面的一整套括号集上 31 // () (()()) 32 // 1 2 第二套括号集可以加过来 33 sum += tmp; 34 max = Math.max(sum, max); 35 } else { 36 // 也可能是一个未完成的括号集，比如： 37 // () (()() 在这里 ()() 是一个未完成的括号集，可以独立出来计算，作为 38 // 阶段性的结果 39 tmp = i - stk.peek(); 40 max = Math.max(tmp, max); 41 } 42 } 43 } 44 45 return max; 46 } 47 }
GIT HUB 代码:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/LongestValidParentheses.java
LeetCode: Longest Valid Parentheses 解题报告
原文：http://www.cnblogs.com/yuzhangcmu/p/4113654.html
