Valid Parentheses
Given a string of brackets ()[]{}, decide whether every bracket is closed by the same type, in the correct order.
A way to picture it
You're stacking pancakes. Every opening bracket puts a pancake on the pile. A closing bracket can only eat the pancake on top — and only if it's the matching flavour. At the end the plate must be empty.
How to approach it
Push openers onto a stack. Each closer must match the top of the stack. Valid means no mismatches and an empty stack at the end.
Example
Input: {"s":"()[]{}"}. Output: true.
Complexity: O(n) time and O(n) space. One pass; the stack can hold up to n openers.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.