Ac solution code


  • 0
    public int longestValidParentheses(String s) {
    	Stack<Integer> stack = new Stack<Integer>();
    	int max = 0, lastMax = 0;
    	for (int i = 0; i < s.length(); i++) {
    		if (s.charAt(i) == '(') {//Push index of '(' 
    			stack.push(i);
    		} else {
    			if (stack.isEmpty()) {//Fail to pair, reset previous pair amount.
    				lastMax = 0;
    			} else { 
    				int curMax = lastMax + (i - stack.pop() + 1);//Succeed to pair, curMax is composed with 2 parts: 1. lastMax 2. (i - stack.pop() + 1) 
    				if (stack.isEmpty())
    					lastMax = curMax;// save curMax to lastMax, e.g. '()()'
    				else
    				    //Stack is not empty means the gap between stack.peek() + 1 and i is available, 
        				//so it's i - (stack.peek()+1) + 1 = i-stack.peek
        				//e.g. (()() = 4
    					curMax = i - stack.peek();
    				max = Math.max(max, curMax);
    			}
    		}				
    	}		
    	return max;
    }

Log in to reply
 

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