有效的括号

🟢 简单

题目描述

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

有效字符串需满足：

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

示例 1

输入：s = "()"
输出：true

示例 2

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

示例 3

输入：s = "(]"
输出：false

示例 4

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

提示

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

解法

参考答案 (2 个标签)

栈 O(n)

思路

遍历字符串，遇到左括号入栈，遇到右括号时检查栈顶是否为对应的左括号。

代码实现

/**
 * @param {string} s
 * @return {boolean}
 */
function isValid(s) {
    const stack = [];
    const pairs = {
        ')': '(',
        ']': '[',
        '}': '{',
    };
    
    for (const char of s) {
        if (char in pairs) {
            if (stack.pop() !== pairs[char]) {
                return false;
            }
        } else {
            stack.push(char);
        }
    }
    
    return stack.length === 0;
}

复杂度分析

时间复杂度：O(n)，遍历一次字符串
空间复杂度：O(n)，最坏情况下栈存储所有左括号

图解

s = "([]){}"

步骤 1: 遇到 '(' → 入栈  stack: ['(']
步骤 2: 遇到 '[' → 入栈  stack: ['(', '[']
步骤 3: 遇到 ']' → 匹配 '[' → 出栈  stack: ['(']
步骤 4: 遇到 ')' → 匹配 '(' → 出栈  stack: []
步骤 5: 遇到 '{' → 入栈  stack: ['{']
步骤 6: 遇到 '}' → 匹配 '{' → 出栈  stack: []
最终: stack 为空，返回 true

上一章节无重复字符的最长子串