Valid Parentheses

L5 Medium Stack

Concept

A stack is the natural tool for nested structures: push openers, and each closer must match the most recent unmatched opener.

A string built from the brackets (), {}, and [] is balanced when every opener is closed by a matching bracket of the same kind, in the correct nested order. Given s, return true if it is balanced.

Examples

▸ s = "()[]{}"

→ true

▸ s = "(]"

→ false

▸ s = "([)]"

→ false

Progressive Hints

Hint 1 · Nudge

A closing bracket must match the very last opener you saw, so a stack is the natural memory.

Hint 2 · Plan

Push openers onto a stack. For each closing bracket: it must match the bracket on top of the stack, and the stack can't be empty. If either fails, return false. At the end the stack must be empty.

Hint 3 · Approach

stack = []. For each c in s: if c is an opener, push its matching closer; else if the stack is empty or its top isn't c, return false; else pop. Return true only when the stack ends empty.

Output

// Run your code to see the output here.