Valid Parentheses
The key idea
Brackets close in last-opened-first-closed order, which is exactly LIFO. Push every opening bracket; on a closing bracket the only valid match is the one on top of the stack. A mismatch or an empty stack means invalid, and a non-empty stack at the end means some opener was never closed.
Problem
Given a string s containing just the characters (, ), {, }, [ and ], determine if the input string is valid.
An input string is valid if all of the following hold:
- Every open bracket is closed by a close bracket of the same type.
- Open brackets are closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Return true if s is valid, and false otherwise.
Constraints
- 1 <= s.length <= 10^4
- s consists of parentheses only
()[]{}.
Examples
Input: s = "()"
Output: true
Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization