20. 有效的括号

Origin: LeetCode 20

题目描述

给定一个只包含 (, ), {, }, [, ] 的字符串 s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合。

示例

Input: s = "()" Output: true

Input: s = "()[]{}" Output: true

Input: s = "(]" Output: false

Input: s = "([)]" Output: false

Input: s = "{[]}" Output: true

约束

• 1 <= s.length <= 10
• s 仅由括号字符组成

关键信息

• 你做过 HackerRank 第 8 题（括号匹配），栈的经典应用
• 左括号 push，右括号 pop 检查是否匹配
• 最后栈空则有效

Resolution

我的解法

function isValid(s: string): boolean {
    const lefts = ['{', '[', '(']
    const rights = ['}', ']', ')']
    const map: { [k: string]: string } = {
        '}': '{',
        ']': '[',
        ')': '('
    }
    const stack = []
    for (let i = 0; i < s.length; i++) {
        let cur = s[i]
        if (lefts.includes(cur)) {
            stack.push(cur)
        } else if (rights.includes(cur)) {
            const poped = stack[stack.length - 1]
            if (map[cur] === poped) {
                stack.pop()
            } else {
                return false
            }
        }
    }
    return !stack.length
}

标准解法（单 map）

function isValid(s: string): boolean {
    const map: { [k: string]: string } = {
        '}': '{',
        ']': '[',
        ')': '('
    }
    const stack = []
    for (const c of s) {
        if (c in map) {
            if (stack.pop() !== map[c]) return false
        } else {
            stack.push(c)
        }
    }
    return !stack.length
}

用 c in map 判断左右括号，不需要 lefts/rights 两个数组。stack.pop() !== map[c] 一行搞定判断+弹出。我的解法的好处是 lefts/rights 可以排除掉非括号字符，更健壮。

栈的经典应用。左括号 push，右括号查栈顶是否匹配：

• 匹配 → pop
• 不匹配 → false
• 遍历完栈空 → true

踩坑

• 最后要检查栈是否为空，return !stack.length，因为可能有未闭合的左括号
• ([)] 是 false：栈顶是 [ 但来了 )，不匹配

复杂度

• 时间：O(n)
• 空间：O(n)