20. 有效的括号

1、题目

2、解法

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> map = new HashMap<Character, Character>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        Stack<Character> stack = new Stack<Character>();

        for (int i = 0; i < s.length(); i++) {
            Character ch = s.charAt(i);
            if (map.containsKey(ch)) {
                Character sh = stack.isEmpty() ? '#' : stack.pop();
                // 如果弹出来的不是，那么false
                if (sh != map.get(ch)) {
                    return false;
                }
            } else {
                stack.push(ch);
            }
        }
        // 最后栈为空，说明是符合要求的
        return stack.isEmpty();
    }
}

时间复杂度O(n),一个个遍历字符，空间复杂度为O(n),遇到的都是左括号

3、思考

@1：如果是一个有效表达式，那么从内向外都是符合要求的括号，那么就可以使用递归的方法，因为没有办法直接进入内部，那么就从外部开始处理，而栈后进先出，可以很好地处理该问题。
@2:加入栈的只能是左括号，这样才能分开二者,所以这里使用HashMap
@弹出栈顶元素，看是否匹配遇到的右括号