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.

Naive Way: 这道题我有一个O(n)的方法，用一个stack只存"("，遇到")"就pop，来确定某一位置是否valid，用一个boolean数组记录valid的情况，最后看这个boolean数组，连续的valid就是连续有效的parentheses。

public class Solution {
    public int longestValidParentheses(String s) {
        boolean valid[] = new boolean[s.length()];
        Stack<Integer> stack = new Stack<Integer>();
        int longest = 0;
        int begin = 0;
        // use stack to determine each position valid or not
        for(int i = 0;i < s.length();i++){
            if(s.charAt(i)=='('){
                stack.push(i);
            }else{
                if(!stack.isEmpty()){
                    valid[stack.pop()]= true;
                    valid[i] = true;
                }
            }
        }
        // get longest valid sequence
        for(int i = 0;i < valid.length;i++){
            if(!valid[i]){
                longest = Math.max(longest, i-begin);
                begin = i+1;
            }
        }
        longest = Math.max(longest,valid.length-begin);
        return longest;
    }
}


Improved Way:这道题非常值得思考，discuss上的做法千奇百怪，大都能在O(n) 的时间和O(n)的space中做出，但是就算一样的复杂度，代码差距还是很大，比如我就发现有一个跟我做法类似，但是不需要多用一个数组去存valid，只需要stack，将invalid的位置push进stack里，最后这些位置会因为没有能匹配的对儿留在stack里，而其他位置都是valid，通过留在stack里的Index可以轻松得到连续有效parentheses的长度。

来自leetcode 用户 blue_y

public int longestValidParentheses(String s) {
    s = ')'+s+'(';
    Stack<Integer> stc = new Stack<Integer>();
    for(int i = 0; i < s.length(); ++i){
        if(s.charAt(i) == ')'){
            if(stc.empty()== false && s.charAt(stc.peek()) == '('){
                stc.pop();
            }
            else
                stc.push(i);
        }else{
            stc.push(i);
        }
    }
    int ans = 0;
    int pre = s.length()-1;
    while(stc.empty() == false){
        ans = Math.max(ans, pre-stc.peek());
        pre = stc.pop();
    }
    return ans-1;
}

以上这两种方案都是O(n) space，discuss里还是有不少人用O(1)的方法做出来的。我看了很多个，都是用了一种方法，就是先从头到尾的扫一遍，求出所有"("有多余的结果，然后从尾到头扫一遍，求出所有")"多余的结果。好厉害。而且这种方法是所有方案中最快的。

public int longestValidParentheses(String s) {
        int longest = 0;
        int stack = 0;
        int i = -1;
        int start = i;
        // 1st scan, head to tail
        while(++i < s.length()){
            stack += s.charAt(i)=='('?1:-1;
            // single ")" at start
            if(stack< 0){
                start = i;
                stack = 0;
            }
            // "(())" found, possible longest
            if(stack==0)
                longest = Math.max(longest, i-start);
        }
        
        // 2nd scan, tail to head
        i = s.length();
        start = i;
        stack = 0;
        while(--i >= 0){
            stack += s.charAt(i)==')'?1:-1;
            // single "(" at tail
            if(stack < 0){
                start = i;
                stack = 0;
            }
            // "(())" found
            if(stack==0)
                longest = Math.max(longest, start-i);
        }
        
        return longest;
    }