Valid Parentheses
Easy· stack· matching
Problem
Given a string made only of the characters ()[]{}, decide whether the brackets are properly matched. Every opener must be closed by the same type, and brackets must close in the reverse order they were opened.
Examples
Input: s = "{[]}()"
Output: true
Input: s = "([)]"
Output: false
The ")" arrives while "[" is still the innermost open bracket.
Constraints
- • 1 <= s.length <= 10^4
- • s contains only bracket characters
Hints & approach
Hint 1
The most recently opened bracket must be the first one closed.
Hint 2
Push openers onto a stack; on a closer, check the top.
Hint 3
Do not forget the case where openers are left over at the end.
Approachtry the hints first
Scan left to right with a stack. Push every opening bracket. For a closing bracket, the stack must be non-empty and its top must be the matching opener; pop it, otherwise return false. After the scan the string is valid only if the stack is empty. A small map from closer to opener keeps the matching check to one line.
Time O(n) · Space O(n)