有效的括号 | LeetCode-20 | 栈与队列

栈与队列练习题

---

LeetCode链接：20. 有效的括号

---

1.题目描述

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

提示：

• $1 <= s.length <= 10^4$
• s 仅由括号 '()[]{}' 组成

2.题解

2.1 栈与队列-哈希集合

class Solution {
    public boolean isValid(String s) {
        // 初始化栈，用于存储需要匹配的右括号
        Stack<Character> stack = new Stack<>();

        // 创建哈希映射，将左括号与相应的右括号配对
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');

        // 遍历字符串的每一个字符
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);

            // 如果字符是左括号（即 map 的键），则将对应的右括号压入栈中
            if (map.containsKey(c)) {
                stack.push(map.get(c));
            } 
            // 如果是右括号，检查栈顶元素是否与当前右括号匹配
            else {
                // 如果栈非空，且栈顶的括号与当前字符匹配，则弹出栈顶元素
                if (!stack.isEmpty() && stack.peek() == c) {
                    stack.pop();
                } else {// 如果不匹配或栈为空，返回 false，表示括号不合法
                    return false;
                }
            }
        }
        return stack.isEmpty();// 最后检查栈是否为空，如果为空则表示所有括号匹配，否则返回 false
    }
}

2.2 栈与队列-逻辑判断

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            // 如何碰到的是键，就入栈
            Character c = s.charAt(i);
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else {
                if (!stack.isEmpty() && stack.peek() == c) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}