Optimized solution for Balanced Parentheses Problem

Question

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Note that an empty string is also considered valid.

Example 1:

Input: "()[]{}"
Output: true
Example 2:

Example 2:

Input: "{[(])}"
Output: false

My solution for the above problem is:

static boolean isPair(char left,char right){
        return left=='{' && right=='}' || left=='(' && right==')' || left=='[' && right==']'; 
    }
    public boolean isValid(String s) {
        Stack<Character> stack= new Stack<>();
        for(char ch: s.toCharArray()){
            if(ch=='(' || ch=='{' || ch=='['){
                stack.push(ch);
            }
            else{
                if(!stack.isEmpty() && isPair(stack.peek(),ch))
                    stack.pop();
                else
                    return false;
            }
        }
        return stack.isEmpty();
}

I have found a much smarter solution somewhere but unable to understand it. Here's the code:

public boolean isValid(String s) {
        Stack<Character> stack= new Stack<>();
        for(char ch: s.toCharArray()){
            if(ch=='(')
                stack.push(')');
            else if(ch=='{')
                stack.push('}');
            else if(ch=='[')
                stack.push(']');
            else if(stack.isEmpty() || stack.pop()!=ch)
                return false;
        }
        return stack.isEmpty();
}

Please help me to understand the working of last else-if block.

Answer 1

You have pushed the closing bracket for all the opening brackets. So, that when closing brackets come, then it will match the character at the top of stack. If it doesn't match or stack becomes empty. That means unbalanced.

else if(stack.isEmpty() || stack.pop()!=ch)
    return false;

When you reach here, you have a bracket as ch but the stack is empty or the value from the stack doesn't match the incoming character.

So, the parantheses are not balanced.