Valid Parentheses
Valid Parentheses is an easy Stack problem from the Blind 75. The key pattern is stack, and a good solution runs in O(n) time.
Problem
Determine whether every bracket in the string is closed by the correct bracket in the correct order.
Examples
Example 1
Input
"{[()]}"Output
trueExample 2
Input
"[](){}"Output
trueExample 3
Input
"{)"Output
falseApproach
Push each opening bracket. Each closing bracket must match the top of the stack, and the stack must be empty at the end.
| Pattern | Stack |
|---|---|
| Time | O(n) |
| Space | O(n) |
Watch out for
A closing bracket on an empty stack makes the string invalid at once.