17. Valid Parentheses
Easy
Monotonic Matching
Stack
Problem
Given a string s containing only the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: 1. Open brackets are closed by the same type of bracket. 2. Open brackets are closed in the correct order. 3. Every closing bracket has a corresponding open bracket.
Examples
Example 1
Input: s = "()"
Output: true
Example 2
Input: s = "()[]{}"Output: true
Example 3
Input: s = "(]"
Output: false
Constraints
� 1 <= s.length <= 10⁴
� s consists only of parentheses characters: ()[]{}.
Hints
?? Use a stack to remember opening brackets.
?? When you encounter a closing bracket, compare it with the most recent opening bracket.
?? At the end, the stack must be empty.
Expected Complexity
Time: O(n)
Space: O(n)
Follow-up
Can you solve it in O(n) time using O(n) auxiliary space?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
"()"Expected
true