My solution using two stacks in one pass, very very easy to understand!


  • 0
    X
    public class Solution {
        public int longestValidParentheses(String s) {
            	Stack<Character> charstack=new Stack<Character>();
    		Stack<Integer> numstack=new Stack<Integer>();
    		int maxlen=0;
    		charstack.push(')');
    		numstack.push(-1);
            for(int i=0;i<s.length();i++)
            {
            	if(s.charAt(i)=='(')
            	{
            		numstack.push(i);
            		charstack.push('(');
            	}
            	else{
            		if(!charstack.isEmpty())
            		{
            			if(charstack.peek()=='(')
            			{        				
            				numstack.pop();
            				charstack.pop();
            				if(i-numstack.peek()>maxlen)maxlen=i-numstack.peek();
            			}
            			else{
            				numstack.push(i);
            				charstack.push(')');
            			}
            		}
            	}
            }
            return maxlen;
        }
    }

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the FAQ for more info. Take a look at good sharing example


Log in to reply
 

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