🟢 有效的括号

📝 题目描述

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

在字符串s中，一个相同的括号字符可出现多次，例如((]]。但有效字符串必须满足以下条件：

左括号必须用相同类型的右括号闭合。例如，(括号必须使用)括号闭合。
左括号必须以正确的顺序闭合，即与数学规则一致。例如，字符串({)}闭合顺序不正确，而字符串({})闭合顺序正确。
每个右括号都必须对应一个相同类型的左括号。
不能为空串""。

📋 代码模版

java

class Solution {
    public boolean isValid(String s) {

    }
}

💡 提示

$1 <= s . l e n g t h <= 10^{4}$
$s$ 仅由 ()[]{}六个括号组成

🚀 示例

🖊️ 题解

该题可以使用「栈」这一数据结构来解决，具体步骤如下。

利用哈希表，建立括号对之间的映射关系。
创建一个栈，用于存放括号字符。
遍历给定的字符串s。在每一轮遍历中，若栈为空或当前字符为左括号（例如'('），则直接将其压入栈中；若当前字符为右括号（例如')'），则判断该右括号是否可将栈顶元素（此时必然存在）闭合，即栈顶元素是否为该右括号对应的左括号，如果对应则将栈顶元素弹出，并进入下一轮遍历，如果不对应则将当前右括号字符压入栈中。
判断辅助栈是否为空。若辅助栈为空，即不包含任何元素，则给定字符串s是有效的；若辅助栈不为空，则给定字符串s是无效的。

⭐️为了进一步提升算法效率，步骤③可使用提前返回方法。在遍历过程中，若当前字符为左括号，则与原步骤保持不变，将其直接压入栈中。而如果当前字符为右括号，此时在判断栈顶元素是否为该右括号对应的左括号时，可提前返回false。需要注意的是，此时可能存在边界问题，即栈顶元素可能不存在（栈为空），在这种情况下，也应提前返回false。

⭐️一个左括号必然需要一个对应的右括号来闭合，因此有效字符串的长度一定为偶数，且不为0（不能为空串""）。若字符串s不符合条件，也可提前返回false。

java

class Solution {
    private final static Map<Character, Character> dict;

    static {
        dict = new HashMap<>(3);
        dict.put('(', ')');
        dict.put('{', '}');
        dict.put('[', ']');
    }

    public boolean isValid(String s) {
        if (s.length() == 0 || s.length() % 2 != 0) {
            return false;
        }
        Deque<Character> charStack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (dict.containsKey(c)) {
                charStack.push(c);
                continue;
            }
            if (charStack.isEmpty() || !Character.valueOf(c).equals(dict.get(charStack.peek()))) {
                return false;
            }
            charStack.pop();
        }
        return charStack.isEmpty();
    }
}

💭 复杂度分析

基于栈的解决方案的复杂度分析如下。

时间复杂度： $O (n)$ ，其中 $n$ 为字符串长度。
空间复杂度： $O (n + | Σ |)$ ，其中 $Σ$ 表示字符集，本题中字符串仅包括6种括号，因此 $| Σ | = 6$ 。栈中的字符数量为 $O (n)$ ，而哈希表使用的空间为 $O (| Σ |)$ ，两者相加即可得到总空间复杂度。

🟢 有效的括号 ​

📝 题目描述 ​

📋 代码模版 ​

💡 提示 ​

🚀 示例 ​

🖊️ 题解 ​

💭 复杂度分析 ​