Tuesday, October 16, 2012

[LeetCode] Longest Valid Parenthese


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.

解题思路:
用两个stack,一个用来装不match的括号符号,另一个装此符号的index。最后得到的stack就是将隔断match符号的位置。相隔的两个index相减就得到了这两个符号的中间的有效括号长度。 


Java Code:

public int longestValidParentheses(String s) {
       Stack index = new Stack();
       Stack parenth = new Stack();
       int maxLen = 0;
       
       for(int i = 0; i < s.length(); i++){
           if(!index.isEmpty() && parenth.peek() == '(' && s.charAt(i) == ')'){
               parenth.pop();
               index.pop();
           }else{
               parenth.add(s.charAt(i));
               index.add(i);
           }
       }
       
       int curr = s.length();
       while(!index.isEmpty()){
           maxLen = maxLen > curr - 1 - index.peek()? maxLen : curr - 1 - index.peek();
           curr = index.pop();
       }
       
       if(curr > 0){
           maxLen = maxLen > curr? maxLen : curr;
       }
       
        return maxLen; 
    }

No comments:

Post a Comment