Check whether a string of brackets is valid.
The short answer
Use a stack: push every opening bracket and pop when you see a closing bracket, checking that it matches the top. If the stack is empty at the end, the string is valid. This is the canonical stack problem — O(n) time, O(n) space.
How to think about it
Recognise the pattern
Any time you need to match the most-recently-opened thing with the current closing token, think stack. Brackets demand exactly that: the innermost open bracket must be closed first — last in, first out.
Build the approach step by step
Brute force: repeatedly strip matched pairs (), [], {} from the string until nothing changes, then check if it is empty. Correct, but O(n²) and awkward.
Stack approach:
- Keep a
stackof unmatched opening brackets. - Scan each character:
- Opening bracket (
(,[,{) → push it. - Closing bracket (
),],}) → if the stack is empty or the top does not match, returnFalse. Otherwise pop.
- Opening bracket (
- After the loop, return
Trueonly if the stack is empty (no unclosed openers left).
The matching is captured cleanly in a dict: closing -> opening.
Input: { [ ( ) ] }
Stack: { → {[ → {[( → {[ → { → empty ✓Complexity
| Value | Why | |
|---|---|---|
| Time | O(n) | Single pass through the string |
| Space | O(n) | Worst case all openers, e.g. "(((((" |