Valid Parentheses

Problem

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

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Solution

Elegant Solution using Stack: O(n) time, O(n) space

public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) return true;
        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(); //cannot just return true here!
    }
}

Analysis

A typical problem to check validation of parentheses
We use Stack because the FILO perfectly satisfies the rules of parentheses
As long as we open a new parenthesis, we must close it first than close any other type of parentheses
Therefore, we loop through every character in s
We find a left parenthesis, we push its right parenthesis into stack
If we find a right parenthesis, we first check if stack is empty
If not, we call pop() and see if it's equal to current parenthesis
At the end, we still need to check isEmpty() to guarantee all parentheses are closed