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.