Valid Parentheses

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: stack

遇到左括号就入栈，遇到右括号查看栈顶左括号是否与当前右括号匹配，匹配继续，否则返回false。最后判断下stack是不是为空，不为空，返回false。

算法的时间复杂度是O(n)，空间复杂度也是O(n)。

public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() <= 1)
            return false;
        
        Stack brackets = new Stack();

        for(int i = 0; i < s.length(); i++) {
            char b = s.charAt(i);
            if(b == '(' || b == '{' || b == '[')
                brackets.push(b);
            else if(b == ')' || b == '}' || b == ']') {
                if(brackets.size() == 0)
                    return false;
                
                if(b == ')' && brackets.peek() == '(')
                    brackets.pop();
                else if(b == '}' && brackets.peek() == '{')
                    brackets.pop();
                else if(b == ']' && brackets.peek() == '[')
                    brackets.pop();
                else 
                    return false;               
            }
        }
        
        if(brackets.size() == 0)
            return true;
        else
            return false;
    }
}