20. 有效的括号 - 简单

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”

输出: true

示例 2:

输入: “()[]{}”

输出: true

示例 3:

输入: “(]”

输出: false

示例 4:

输入: “([)]”

输出: false

示例 5:

输入: “{[]}”

输出: true

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/valid-parentheses

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() % 2 != 0) return false;
        //if (s.length() == 0) return true;
        char[] cs = s.toCharArray();
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : cs) {
            if (c == '(' || c == '{' || c == '['){
                stack.push(c);
            }else {
                Character last = stack.poll();
                if (last == null) return false;
                if (c == ')') {
                    if (last != '(') return false;
                } else{
                    if((c - 2) != last) return false;
                }
            }
        }
        return stack.size() == 0;
    }
}

减少栈储存耗时

    class Solution {
        public boolean isValid(String s) {
            char[] res = new char[s.length() + 1];
            int index = 1;
            for (char tmp : s.toCharArray()) {
                if (tmp == '(' || tmp == '{' || tmp == '[') {
                    res[index++] = tmp;
                } else {
                    index--;
                    if (tmp == ')' && res[index] != '(') {
                        return false;
                    }
                    if (tmp == '}' && res[index] != '{') {
                        return false;
                    }
                    if (tmp == ']' && res[index] != '[') {
                        return false;
                    }
                }
            }
            return index == 1;
        }
    }