leetcode -- 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.

Version 1

仅仅考虑了()()这种情况，当input:()(())时输出为2，expected为:6

(())也是valid parentheses

 1 public class Solution {
 2     public int longestValidParentheses(String s) {
 3         // Start typing your Java solution below
 4         // DO NOT write main() function
 5         int max = 0;
 6         int len = s.length();
 7         Stack<Character> stack = new Stack<Character>();
 8         int lastIndex = -1;
 9         
10         int curLen = 0;
11         for(int i = 0; i < len; i++){
12             if(!stack.empty()){
13                 char top = stack.peek();
14                 char c = s.charAt(i);
15                 
16                 if(match(top, c)){
17                     if(i - lastIndex == 2){
18                        curLen += 2; 
19                        lastIndex = i;
20                        if(curLen > max){
21                             max = curLen;
22                        }
23                     } else {
24                         curLen = 2;
25                         if(curLen > max){
26                             max = curLen;
27                         }
28                         lastIndex = i;
29                     }
30                     stack.pop();
31                 } else {
32                     stack.push(c);
33                 }
34             } else {
35                 char c = s.charAt(i);
36                 stack.push(c);
37             }
38         }
39         
40         return max;
41     }
42     
43     boolean match(char a, char b){
44         if(a == '(' && b == ')'){
45             return true;
46         } else {
47             return false;
48         }
49     }
50 }

Version 2：

通过维护一个左边界来计算Longest Valid Parentheses

 1 class Node{
 2     char c;
 3     int i;
 4     public Node(char c, int i){
 5         this.c = c;
 6         this.i = i;
 7     }
 8 }
 9 
10 public class Solution {
11     public int longestValidParentheses(String s) {
12         // Start typing your Java solution below
13         // DO NOT write main() function
14         int max = 0;
15         int len = s.length();
16         Stack<Node> stack = new Stack<Node>();
17         int lastIndex = -1;
18         
19         int curLen = 0;
20         for(int i = 0; i < len; i++){
21             if(!stack.empty()){
22                 Node top = stack.peek();
23                 char c = s.charAt(i);
24                 
25                 if(match(top.c, c)){
26                     stack.pop();
27                     if(stack.empty()){
28                         max = Math.max(max, i- (-1));
29                     } else{
30                         max = Math.max(max, i - (stack.peek()).i);
31                     }
32                     
33                 } else {
34                     stack.push(new Node(c, i));
35                 }
36             } else {
37                 char c = s.charAt(i);
38                 stack.push(new Node(c, i));
39             }
40         }
41         
42         return max;
43     }
44     
45     boolean match(char a, char b){
46         if(a == '(' && b == ')'){
47             return true;
48         } else {
49             return false;
50         }
51     }
52     
53 }

参考：http://fisherlei.blogspot.com/2013/03/leetcode-longest-valid-parentheses.html

http://www.cnblogs.com/remlostime/archive/2012/11/25/2787878.html

对代码进行重构，'('只会入栈，')'可能入栈，可能出栈

Version 3

 1 class Node{
 2     char c;
 3     int i;
 4     public Node(char c, int i){
 5         this.c = c;
 6         this.i = i;
 7     }
 8 }
 9 
10 public class Solution {
11     public int longestValidParentheses(String s) {
12         int max = 0;
13         int len = s.length();
14         Stack<Node> stack = new Stack<Node>();
15         stack.push(new Node(')', -1));        
16         int curLen = 0;
17         for(int i = 0; i < len; i++){
18             char c = s.charAt(i);
19             if(c == '('){
20                 stack.push(new Node(c, i));
21             } else {
22                 Node top = stack.peek();
23                 if(top.c == '('){
24                     stack.pop();
25                     max = Math.max(max, i - stack.peek().i);
26                 } else {
27                     stack.push(new Node(c, i));
28                 }
29             }
30         }
31         return max;
32     }
33 }