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 }

View Code

2015.1.3 redo:

 1 public class Solution {
 2     public int longestValidParentheses(String s) {
 3         if (s == null) {
 4             return 0;
 5         }
 6         
 7         int len = s.length();
 8         Stack<Integer> stk = new Stack<Integer>();
 9         
10         int sum = 0;
11         int max = 0;
12         for (int i = 0; i < len; i++) {
13             char c = s.charAt(i);
14             if (c == '(') {
15                 stk.push(i);
16             } else {
17                 if (stk.isEmpty()) {
18                     // The sequence is cut off.
19                     sum = 0;
20                 } else {
21                     int tmp = i - stk.pop() + 1;
22                     if (stk.isEmpty()) {
23                         sum += tmp;
24                         max = Math.max(max, sum);
25                     } else {
26                         max = Math.max(max, i - stk.peek());
27                     }
28                 }
29             }
30         }
31         
32         return max;
33     }
34 }

View Code

GIT HUB 代码:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/LongestValidParentheses.java