IT 面试题库

编程题:给定一个只含 `()[]{}` 的字符串,判断它是否有效(LeetCode 20)。有效要求:括号类型匹配、顺序正确、正确闭合。为什么这道题天然适合用栈?

中级编程题算法工程师Java后端工程师栈括号匹配LeetCode20LIFO

题目

考察点:栈「后进先出」与最近匹配原则的结合,是从链表转向栈类题的衔接点。追问:如果字符串里混入其他字符,如何调整?

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 72 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

要点:左括号压栈、右括号弹栈比对——「最近未闭合的左括号必须最先被闭合」正好是栈的 LIFO 语义。

def isValid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch not in pairs:          # 左括号
            stack.append(ch)
        elif not stack or stack.pop() != pairs[ch]:
            return False             # 右括号不匹配/栈空
    return not stack                 # 必须全部闭合
练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题