跳到主要内容

1 / 4思路

Valid Parentheses

原题

思路​

左括号入栈;右括号必须和栈顶配对。扫描结束后栈为空才算有效。用映射表把三种右括号映射到对应的左括号,避免写三段分支。

复杂度​

  • 时间 O(n):每个字符进出栈一次。
  • 空间 O(n):最坏全是左括号。

代码​

def is_valid(s: str) -> bool:
pairs = {")": "(", "]": "[", "}": "{"}
stack: list[str] = []
for char in s:
if char in pairs:
if not stack or stack.pop() != pairs[char]:
return False
else:
stack.append(char)
return not stack

边界​

  • 奇数长度:一定无效,可提前返回。
  • 先出现右括号:栈为空,返回 false。
  • 只有左括号:扫描结束栈非空,返回 false。