首页 > 代码库 > LeetCode: Longest Valid Parentheses 解题报告
LeetCode: Longest Valid Parentheses 解题报告
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 解题报告