Leetcode 有效的括号

Day 8 第1题

力扣官方解题思路：利用栈的特性和哈希表快速配对及时把括号数组pop出去，关键在于左右括号需要连续封闭：stack.peek() != pairs.get(ch)。

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            // 通过hashmap来判断链表是否括号匹配
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        LinkedList<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            System.out.println(stack.peek());
            char ch = s.charAt(i);
            // 如果出现右括号
            if (pairs.containsKey(ch)) {
                // 栈顶元素
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                // 匹配后弹出左括号
                stack.pop();
            } else {
                // 把左括号推入栈
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

创建栈：利用java的栈类来创建：Stack<String> s = new Stack<String>(); stack的方法包括pop()，push()，peek()，isEmpty()，size()

java的linkedlist：在节点内存储下一个节点的地址，分为双向链表和单向链表，LinkedList<E> list = new LinkedList<E>();，查询和访问操作不便捷。

回顾一下java的arraylist，ArrayList<E> list = new ArrayList<E>();，包括add，set，remove，get，size等方法。