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

public class Solution {
    public boolean isValid(String s) {
        if(s == null) return false;

        Stack<Character> st = new Stack<Character>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);  
            if(c == '(' || c == '{' || c == '[') {
                st.push(c);
            } else {
                if(st.size() == 0) {
                    return false;
                }
                // pop out stack top to see if it matches
                char cur = st.pop();

                if(c == ')') {
                    if(cur != '(') return false;
                } else if(c == '}') {
                    if(cur != '{') return false;
                } else if(c == ']') {
                    if(cur != '[') return false;
                } else {
                    return false;
                }
            }
        }

        if(st.size() == 0) 
            return true;
        else
            return false;
    }
}