Problem Statement
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.
Approach
Use a stack to track opening brackets. For each closing bracket, check if it matches the top of the stack.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
Examples
Example 1
Input: s = "()"
Output: true
Example 2
Input: s = "()[]{}"
Output: true
Example 3
Input: s = "(]"
Output: false
Constraints
- ▸
1 <= s.length <= 10^4 - ▸
sconsists of parentheses only()[]{}}
Loading...
Sign in to run your code...
Asked by companies:
AmazonFacebookBloombergGoogle