Accepted java solution, stack storing width, not index


  • 0
    T

    is much longer and not as elegant as the solution to store index, but it offers another perspective, and is more general, in that if the problem asked for an abitrary function , or if the input string is allowed to contain ignorable chars besides '(' and ')', the index-based solution would not be valid. ( for example, "(0()0)" as input, the '0' can be ignored, then the original approach to find the enclosing length by j-left can't prune the length of "0" )

    public class Solution {
    public int longestValidParentheses(String s) {
        int ptr = 0;
        int runningLength = 0;
        int best = 0;
        Stack<Integer> stack = new Stack<Integer>();
        while( ptr < s.length()) {
            char c = s.charAt(ptr);
            if (c == ')') {
                if (stack.empty()) {
                    // a wasted char
                    runningLength = 0;
                } else {
                    int widthAtThisLevel = stack.pop();
                    // ( .....100....()    in this example, the right-most )  pops the "(", then pops the existing accumulated 100, and pushes it back
                    widthAtThisLevel +=2;
                    if ( stack.empty() ) {
                        // record best
                        runningLength += widthAtThisLevel; // take care of cases like (....) (....) at the root level
                        if (runningLength > best)
                            best = runningLength;
                    } else {
                    int accumulatedAtParentLevel = stack.pop();
                    stack.push(accumulatedAtParentLevel + widthAtThisLevel); // note that it's still open ---- we did not +2
                                        if (stack.peek() > best) best = stack.peek();
    
                    }
                }
            } else {// '('
                stack.push(0);
            }
            
            ptr++;
        }
        
        // if ( !stack.empty()) {
        //     int width = stack.pop();
        //     if (width > best) best = width;
        // }
        return best;
    }
    

    }


Log in to reply
 

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