Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Examples
Example 1
Input: s = "()[]{}"
Output: true
Explanation: Each opening bracket is matched by the same type of closing bracket in the correct order.
Example 2
Input: s = "([)]"
Output: false
Explanation: The brackets are not closed in the correct order — the '[' is closed by ')' before the '(' is closed.
Example 3
Input: s = "{[]}"
Output: true
Explanation: The '[' inside '{}' is properly closed before the outer '{' is closed.
Constraints
- -1 <= s.length <= 10^4
- -s consists of parentheses only '()[]{}'.
Optimal Complexity
Time
O(n)
Space
O(n)
Practice this problem with an AI interviewer
TechInView conducts a full voice mock interview — the AI asks clarifying questions, evaluates your approach, watches you code, and scores you on 5 dimensions. Just like a real FAANG interview.
Start a free interview