博客

题目：

思路：用一个map存储成对的括号，用一个栈结构存储String中的左括号。当开始遇到右括号时，就要消耗栈顶的一个左括号，然后根据这个左括号去map查对应的右括号，如果查到的右括号与当前遇到的右括号类型不一致，则直接false

但是当一开始就是右括号时，stack.pop()会报错，所以加多一个垫底。

class Solution {
    public boolean isValid(String s) {
        if (s.length()%2==1){
            return false;
        }
        HashMap<Character, Character> map = new HashMap<>();
        map.put('{', '}');
        map.put('[', ']');
        map.put('(', ')');
        map.put('*', '*');//当String以右括号开始时，pop空指针异常，所以加多一个

        Deque<Character> stack = new LinkedList<>();
        stack.push('*');//当String以右括号开始时，pop空指针异常，所以加多一个，String中只有括号，所以 *一定不会等于括号，直接false


        for (Character c : s.toCharArray()) {

            if (map.containsKey(c)) { //左括号入栈
                stack.push(c);
            }
            else if (map.get(stack.pop()) != c) { //若为右括号，需消耗栈里的左括号，如果括号类型不匹配，则失败
                return false;

            }

        }
        return stack.size()==1;
    }
}