The problem. Given a string s containing only the characters (, ), [, ], { and }, decide whether it is valid: every opening bracket is closed by the same type of bracket, and brackets close in the correct order — the most recently opened bracket closes first.
![Three examples. {[()]} is valid: each pair nests inside the next. ()[]{} is valid: the pairs sit side by side. ([)] is invalid: the [ is still open when ) tries to close the (, so the pairs cross.](/drawings/e53a1b1d-b0d4-4ad6-8fd9-ed08d062a8c1.svg)
Input: s = "()[]{}" Output: true
Input: s = "(]" Output: false
Input: s = "([)]" Output: false
Input: s = "{[]}" Output: trueCounting isn't enough: ([)] has one of each bracket, yet it's invalid. What matters is the order: a closing bracket must match the most recent bracket that is still open.
Free account
Sign up to read the rest of this lesson: 5 more sections, 3 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.
Still to come