Leetcode–Longest Valid Parentheses

The Problem:

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.

Notes:

  1. Wrong way: I was thinking of using stack, and each time find a pair then pop that pair. Then realized that the stack will only contain ‘(‘, since each time a ‘)’ come, instead of pushing it, a ‘(‘ will be popped. So I switched to only use a counter to record the number of ‘(‘. But consider this case: “(()()” and “()(()”, although they follow the same number of ‘(‘ and ‘)’, we need to record the location of unmatched ‘(‘ !
  2. Solution I: use a stack of integer to record the indices of unpaired ones. So each ‘(‘ will be pushed into stack, and for each ‘)’, if no ‘(‘ can match (stack empty, or stack top is a ‘)’ ), then also push into stack. otherwise pop a ‘(‘. In this fashion only peek the top can know the last unpaired index, by subtracting it we can get the valid length.
  3. Solution II: a less straight forward DP solution I found online. Use an array vlen to record the valid length of parentheses ending with s[i]. For each ‘(‘, it will have vlen[i] = 0; for each ‘)’, check the index of precous ‘free’ char, which is at j=(i-1-vlen[i-1]), see if it’s a ‘(‘, if true then can be paired, and vlen[i]=vlen[i-1]+2, and do NOT forget to also merge with vlen[j-1] !

Java Solution I:

public class Solution {
    public int longestValidParentheses(String s) {
        // use a stack to record unpaired indices
        Stack<Integer> st = new Stack<Integer>();
        int valid = 0;
        int max = 0;
        for(int i = 0; i < s.length(); i++){
             // 1. it's a '(' ; 2. it's a ')' but no '(' left to match
            if(s.charAt(i)=='(' || st.empty()|| s.charAt(st.peek())==')'){
                st.push(i);
            }
            else{
                st.pop();
                if(st.empty()){
                    // note here is i+1, not i !
                    valid = i+1;
                    max = valid;
                }
                else{
                    valid = i-st.peek();
                    max = Math.max(max, valid);
                }
            }            
        }
        return max;        
    }
}

Java Solution II:

public class Solution {
    public int longestValidParentheses(String s) {
        if(s.length()==0)return 0;
        //valid length ending at i
        int[] vlen = new int[s.length()];
        vlen[0]= 0;
        int max = 0;
        for(int i = 1; i < s.length(); i++){
            if(s.charAt(i)=='('){
            // valid parenthese cannot end with '('
                vlen[i] = 0;
            }
            else{
                int j = i-1-vlen[i-1];
                //can match with a previous '('
                if(j>=0 && s.charAt(j)=='('){
                    vlen[i] = vlen[i-1]+2;
                    // connect with the length before j
                    if(j-1>=0){
                        vlen[i] += vlen[j-1];
                    }
                }                
            }
            max = Math.max(max, vlen[i]);
        }
        return max;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s