有效括号

Leetcode题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "([)]"
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

栈解答

经典的括号问题，在类似成双匹配对的机制，可以采用Hashmap进行对应存储。然后使用栈进行一一匹配，判断栈时是否为空而已。

• 特性一：无论字符串中有什么样的元素，如果是出现奇数个，那么一定是不匹配的。
• 特性二：减少大量if-else语句的方式可以采用哈希表的方式转换对应。

Demo

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>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        // 入栈判断，左符号入栈
        for (int i = 0; i < n; i++) {
            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();
    }
}

小结

使用栈

Deque<Character> stack = new LinkedList<Character>(); // 可以创建的一种方式
Stack<Character> stack = new Stack<Character>(); //两种方式都可以创建

栈的基本函数

Peek() 查看栈顶元素但不删除
Pop() 返回栈顶元素并且删除
push(c) 元素c推入栈顶

减法 默认闭区间 5-3 =2