leetcode-20.有效的括号

题目链接

20. 有效的括号

代码

class Solution {

    // Map.of 是 Java 9 及以后有的 api
    private static final Map<Character, Character> pairs = Map.of('(', ')', '{', '}', '[', ']');

    public boolean isValid(String s) {

        // 栈推荐使用 Deque 而不是 Stack
        Deque<Character> stack = new ArrayDeque<>();

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

            if (pairs.containsKey(c)) {
                // 如果是 左边括号，就把 右边括号放进去
                stack.push(pairs.get(c));
            } else if (stack.isEmpty() || stack.pop() != c){
                // 如果是 右边括号，就 pop 出来看是不是一样
                return false;
            }
        }

        return stack.isEmpty();
    }
}

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(n+∣Σ∣)