All DSA problems
EasyStack & QueueGoogleAmazonMeta
Valid Parentheses
Given a string s containing only ()[]{}, determine if the input string is valid.
A string is valid if:
1. Open brackets are closed by the same type.
2. Open brackets are closed in the correct order.
3. Every close bracket has a corresponding open bracket.
Print true or false.
**Input:** one line string
Examples
Example 1
Input:
()
Output: true
Example 2
Input:
()[]{}Output: true
Example 3
Input:
(]
Output: false
Example 4
Input:
([)]
Output: false
Constraints
- 1 ≤ s.length ≤ 10^4
- s consists of ()[]{} only
Target: O(n) time · O(n) space