easy

Valid Parentheses

Given a string containing only the characters ()[]{}, decide whether it is well-formed: every opening bracket is closed by the same type in the correct nested order.

Constraints

1 ≤ s.length ≤ 10^4
s consists only of ()[]{}

Examples

in: s = "()[]{}"

out: true

in: s = "([)]"

out: false

Recognition clues

Nested matching — the most recent opener must close first
Last-in, first-out
Mismatch or leftover openers mean invalid

Pattern

Stack

Nesting and "last opened must be first closed" are LIFO by definition, so a stack tracks the currently open context. Any recursive process can also be flattened onto an explicit stack, which is how iterative DFS and expression parsers work.

Stack String

Solution

Scan the string with a stack. Push every opening bracket. On a closing bracket, the stack must be non-empty and its top must be the matching opener; pop it, otherwise return false. After the scan the string is valid only if the stack is empty. The stack mirrors the nesting exactly.

time O(n)space O(n)

Alternative approaches

A single counter works only for one bracket type; repeatedly deleting adjacent pairs from the string is O(n^2).

Code it yourself

Solve in

Hints:

Learn Stack ▶ Visualize