Stack · 014Easy
Valid Parentheses
Given a string s containing only the characters '()[]{}', determine whether the input is valid: brackets must close in the correct order and be of the same type.
Constraints
- 1 <= s.length <= 10^4
- s consists only of the characters '()[]{}'.
Examples
isValid("()") -> true
isValid("()[]{}") -> true
isValid("(]") -> false
isValid("([)]") -> false // wrong nesting order
isValid("(") -> false // odd length; stack still non-empty at the end
isValid("())") -> false // closer with an empty stackEdge cases
- Odd-length strings can never be valid.
- A closing bracket with an empty stack is invalid.
- A non-empty stack at the end is invalid.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — repeatedly strip out adjacent matching pairs.
- Target
- O(n) time, O(n) space — push openers onto a stack and pop-match on every closer.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/04-stack/014-valid-parentheses.js ./practice c 014