括号匹配

算法思路

用栈维护尚未匹配的左括号，从左到右扫描字符串：

• 遇到 (, [, {：入栈
• 遇到 ), ], }：栈空或栈顶与当前右括号不匹配则返回 false；否则弹出栈顶
• 其他字符忽略
• 扫描结束栈为空则匹配成功

时间 O(n)，空间 O(n)。

python

def is_valid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []

    for ch in s:
        if ch in pairs: # 认为应该是成对的，如果不成对就false
            if not stack or stack.pop() != pairs[ch]:
                return False
        elif ch in "([{":
            stack.append(ch)

    return not stack

js

function isValid(s) {
    const pairs = { ")": "(", "]": "[", "}": "{" };
    const stack = [];

    for (const ch of s) {
        if (pairs[ch]) {
            if (!stack.length || stack.pop() !== pairs[ch]) {
                return false;
            }
        } else if ("([{".includes(ch)) {
            stack.push(ch);
        }
    }

    return stack.length === 0;
}

go

func isValid(s string) bool {
    pairs := map[byte]byte{')': '(', ']': '[', '}': '{' }
    stack := make([]byte, 0, len(s))

    for i := 0; i < len(s); i++ {
        ch := s[i]
        if open, ok := pairs[ch]; ok {
            n := len(stack)
            if n == 0 || stack[n-1] != open {
                return false
            }
            stack = stack[:n-1]
        } else if ch == '(' || ch == '[' || ch == '{' {
            stack = append(stack, ch)
        }
    }

    return len(stack) == 0
}