有效的括号匹配

题目

有效的括号匹配

信息

• 类型：问答
• 难度：⭐

考点

栈的基本操作, 字符串处理, 边界条件处理

快速回答

使用栈数据结构检查括号字符串是否有效：

• 遍历字符串，遇到左括号入栈
• 遇到右括号时检查栈顶是否匹配
• 匹配则弹出栈顶，否则返回无效
• 最终栈为空则有效，否则无效

原理说明

栈的后进先出(LIFO)特性非常适合处理括号匹配问题：

1. 遇到左括号 (, [, { 时入栈
2. 遇到右括号 ), ], } 时：
   • 若栈为空 → 无效（右括号多余）
   • 若栈顶不匹配 → 无效
   • 若匹配则弹出栈顶
3. 遍历结束后栈为空才有效

代码示例（Python）

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in mapping:  # 遇到右括号
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:  # 遇到左括号
            stack.append(char)

    return not stack  # 栈空才有效

最佳实践

• 使用字典存储括号映射关系，提高可扩展性
• 提前处理空字符串返回 True
• 时间复杂度 O(n)，空间复杂度 O(n)

常见错误

• 未检查栈空直接 pop() → 导致运行时错误
• 忘记处理遍历结束栈非空的情况 → 漏判左括号多余
• 错误映射括号关系（如 ')' 映射到 ']'）

扩展知识

• 实际应用：编译器语法检查、JSON/XML解析器
• 变体问题：带文本内容的括号匹配（如 HTML 标签）
• 优化方向：添加长度奇偶校验提前返回（奇数长度必无效）