My 4ms Java Solution with double stack


  • 0
    F
    public class Solution {
        public int longestValidParentheses(String s) {
            if(s==null || s.length()==0){
                return 0;
            }
            int cnt;
            int[] indexStack = new int[ s.length() ];
            int[] bracketStack = new int[ s.length() ];
            int isPtr, bsPtr;
            int curUpper, curLower, maxUpper, maxLower, maxLen;
            
            for(isPtr = bsPtr = -1, cnt = 0; cnt < s.length(); cnt++){
                if(s.charAt(cnt) == '('){
                    indexStack[ ++isPtr ] = cnt;
                } else if(isPtr > -1) {
                    bracketStack[ ++bsPtr ] = indexStack[ isPtr-- ];
                    bracketStack[ ++bsPtr ] = cnt;
                }
            }
            
            if(bsPtr == -1){
                return 0;
            }
            maxUpper = bracketStack[ bsPtr-- ];
            maxLower = bracketStack[ bsPtr-- ];
            maxLen = 2;
            while(bsPtr > -1){
                curUpper = bracketStack[ bsPtr-- ];
                curLower = bracketStack[ bsPtr-- ];
                if(curUpper == maxLower-1){
                    maxLower = curLower;
                } else if(curUpper < maxLower-1) {
                    maxLen = Math.max(maxLen, maxUpper-maxLower+1);
                    maxUpper = curUpper;
                    maxLower = curLower;
                }
            }
            
            return Math.max(maxUpper-maxLower+1, maxLen);
        }
    }
    

    In the first pass, I push the start and the end of every pair of parenthesis into bracketStack. So, every time I pop out a new pair from the bracketStack, if it's incorporated in the previous parenthesis, the maximum length remains unchanged. If its upper bound is only 1 less than then lower bound of the previous parenthesis, then these two are concatenated into a longer substring. If its upper bound is less than the lower bound of the previous parenthesis by more than one, then it's a new substring, and I'll need to save the current maximum length.


Log in to reply
 

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