LeetCode-有效的括号（020）

一.题目描述

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

有效字符串需满足：

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

二.示例 

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

三.提示：

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

四.解法:

方法一：栈

遍历括号字符串 s，遇到左括号时，压入当前的左括号；遇到右括号时，弹出栈顶元素（若栈为空，直接返回 false），判断是否匹配，若不匹配，直接返回 false。

也可以选择遇到左括号时，将右括号压入栈中；遇到右括号时，弹出栈顶元素（若栈为空，直接返回 false），判断是否是相等。若不匹配，直接返回 false。

两者的区别仅限于括号转换时机，一个是在入栈时，一个是在出栈时。

遍历结束，若栈为空，说明括号字符串有效，返回 true；否则，返回 false。

时间复杂度 O(n)，空间复杂度 O(n)。其中 n 为括号字符串 s 的长度。

五.代码

Java代码

class Solution {
    public boolean isValid(String s) {
        // 使用双端队列作为栈来存储左括号
        Deque<Character> stk = new ArrayDeque<>();
        
        // 遍历字符串中的每个字符
        for (char c : s.toCharArray()) {
            // 如果是左括号，压入栈中
            if (c == '(' || c == '{' || c == '[') {
                stk.push(c);
            } else if (stk.isEmpty() || !match(stk.pop(), c)) {
                // 如果是右括号，检查栈是否为空或栈顶元素是否匹配
                return false;
            }
        }
        
        // 如果栈为空，说明所有括号匹配成功
        return stk.isEmpty();
    }

    // 辅助函数，用于检查括号是否匹配
    private boolean match(char l, char r) {
        return (l == '(' && r == ')') || (l == '{' && r == '}') || (l == '[' && r == ']');
    }
}

注释说明
    ·栈的使用：使用 Deque 作为栈来存储左括号，方便后续匹配。
    ·遍历字符串：逐个检查字符串中的字符。
        ·左括号处理：如果是左括号，直接压入栈中。
        ·右括号处理：如果是右括号，检查栈是否为空或栈顶元素是否匹配。
            ·如果栈为空或不匹配，返回 false。
    ·匹配检查：使用辅助函数 match 检查当前右括号是否与栈顶左括号匹配。
    ·最终检查：遍历结束后，检查栈是否为空，若为空则所有括号匹配成功，返回 true。

🌟 关注我的CSDN博客，收获更多技术干货！ 🌟