The problem
Given a string s of the characters (, ), [, ], { and }, decide whether it is valid.
It is valid when every opening bracket is closed by the same kind of bracket, brackets close in the right order (the most recently opened first), and every closing bracket has an opening one.
Examples
01
- Input
s = "()"
- Output
true
02
- Input
s = "()[]{}"- Output
true
03
- Input
s = "(]"
- Output
false
Constraints
- 1 ≤ s.length ≤ 10⁴
shas only the six bracket characters.
The idea
The bracket that must close next is always the most recently opened one still open. “Most recent first” is exactly what a stack gives.
Push each opening bracket. At a closing bracket, the top of the stack must be its partner: pop it, or fail if it is the wrong kind or the stack is empty. At the end, anything left on the stack was never closed.
- Time
- O(n)
- Space
- O(n) — the stack
Solution · every language run against every case
class Solution: def isValid(self, s: str) -> bool: pairs = {')': '(', ']': '[', '}': '{'} stack = [] # opening brackets still waiting for their closer for c in s: if c in pairs: if not stack or stack.pop() != pairs[c]: return False else: stack.append(c) return not stack