20 Valid Parentheses

20 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.

分析及代码

伪代码：

用一个stack，各式左括号都放进去，碰到右括号的时候，就检查
    是不是stack为空，为空就false
    是不是匹配，不匹配false
最后检查完了,有可能有左括号比右括号多的情况，返回stack.isEmpty()

代码：

public boolean isValid(String s) {
    if(s == null || s.length() == 0 || s.length() % 2 != 0) {
        return false;
    }
    Deque<Character> stack = new ArrayDeque<>();
    int len = s.length();
    for(int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if(c == '{' || c == '[' || c == '(') {
            stack.offerLast(c);
        } else {
            if(stack.isEmpty()) {
                return false;
            }
            char pre = stack.pollLast();
            if((c == '}' && pre == '{') || (c == ']' && pre == '[') || (c == ')' && pre == '(')) {
                continue;
            }
            return false;
        }
    }
    return stack.isEmpty();
}

O(length)