Direct solution with one stack


  • 1
    D
    /*
    use a stack to store parentheses and length of already matched pairs.
    e.g.,
    input: ) ( ( ) ) ( )
           0 1 2 3 4 5 6
    We scan )(( and store in stack, after scanned ')' in 3rd position, we find it match with 
    '(' in 2rd position so pop '(' and push number 2(length of matched pair) to stack. The 
    current stack is [), (, 2].
    
    Then scan 4th position , it matches 1st position, because we have a matched pair between 
    them, pop twice, and push (2+2=4), we call this indirect match. The current stack is 
    [), 4], then scan 5th position, nothing happens. The current stack is [), 4, (].
    
    Then we find a direct match ('(' follows ')' directly) and the previous item in stack is 
    a number 4,  we have to merge consecutive numbers, and the final stack will be [), 6].
    
    Finally, we pop all the items in stack and find the largest number, that's the max length.
    
    As you see, all the tricks happen in indirect match and merge consecutive numbers, and
    recursion happens at most twice for one call, because we will merge every consecutive 
    numbers as long as them exist, so the time-complexity is O(N). 
    Actually, we can use just Array because the biggest capacity of stack is s.length();
    */
    public class LongestValidParentheses {
    public static int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        // use negative value to store '(' and ')', we will use 
        // positive value to store length of valid parentheses 
        for (int i = 0; i < s.length(); i++)
            add(stack, -s.charAt(i));
        int maxLen = 0;
        while (!stack.empty()) {
            int a = stack.pop();
            if (a > maxLen) maxLen = a;
        }
        return maxLen;
    }
    
    private static void add(Stack<Integer> stack, int now) {
        if (stack.empty()) {
            stack.push(now);
        } else if (isParenthese(now)) {
            int last = stack.peek();
            if (isParenthese(last)) { // [stack, parenthese, parenthese]
                if (match(last, now)) { // just match
                    stack.pop();
                    add(stack, 2); // use recursion to merge possible consecutive numbers
                } else {
                    stack.push(now);
                }
            } else { // [stack, number, parenthese]
                stack.pop();
                if (stack.empty()) { // [number, parenthese]
                    stack.push(last);
                    stack.push(now);
                } else {
                    int llast = stack.peek();
                    if (isParenthese(llast)) { // [stack, parenthese, number, parenthese]
                        if (match(llast, now)) { // match and merge
                            stack.pop();
                            add(stack, 2 + last); // possible merge of consecutive numbers
                        } else {
                            stack.push(last);
                            stack.push(now);
                        }
                    } else { // [stack, number, number, parenthese]
                        // Not possible. All the consecutive numbers will be 
                        // merged before this case happens
                    }
                }
            }
        } else { // now is a number
            int last = stack.peek();
            if (!isParenthese(last)) { // [stack, number, number], merge
                stack.pop();
                // no need to use recursion because previous 
                // consecutive numbers are already merged
                stack.push(last + now);
            } else { // [stack, parenthese, number]
                stack.push(now);
            }
        }
    }
    
    private static boolean isParenthese(int ch) {
        return -ch == '(' || -ch == ')';
    }
    
    private static boolean match(int a, int b) {
        return -a == '(' && -b == ')';
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.