20.有效的括号 Easy

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

有效字符串需满足：

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

示例 1：
输入：s = "()"
输出：true

示例 2：
输入：s = "()[]{}"
输出：true

示例 3：
输入：s = "(]"
输出：false

示例 4：
输入：s = "([])"
输出：true

解题思路

输入：一个只包含 '({[]})' 的字符串 s

输出：判断字符串是否有效

本题属于典型的 合法括号栈 问题。

我们使用一个栈 stack 来模拟字符的处理过程：

1. 遍历字符串中的每个字符；
2. 每次入栈前，先判断当前字符是否是左括号 ([{
   • 如果是，就直接入栈
   • 否则，就判断当前字符是否和栈顶符号是相互匹配的，如果没有栈顶元素或不匹配则直接判定不合法，如果匹配则直接弹出栈顶元素
3. 遍历结束后，判断栈中是否还剩余未匹配的左括号，没有剩余则都匹配完毕合法

代码实现

python

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []  # 栈用于保存未匹配的左括号
        # 括号对映射表：右括号作为 key，左括号作为 value
        mapping = {')': '(', ']': '[', '}': '{'}

        # 遍历每个字符
        for c in s:
            if c in mapping.values():
                # 如果是左括号，压入栈
                stack.append(c)
            else:
                # 如果是右括号，检查是否匹配栈顶
                if not stack or stack[-1] != mapping[c]:
                    return False  # 栈空或不匹配，说明不合法
                stack.pop()  # 匹配成功，弹出栈顶左括号
        
        # 最终栈为空表示所有括号都匹配成功
        return not stack

javascript

const isValid = function(s) {
    const stack = [];

    const map = {')': '(', ']': '[', '}': '{'};

    for (let c of s) {
        if (Object.values(map).includes(c)) {
            stack.push(c);
        } else {
            if (!stack.length || stack.at(-1) !== map[c]) 
                return false;

            stack.pop();
        }
    }

    return !stack.length;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

20 国际版

20 中文版