Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']'.
A string s 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.
Return true if s is valid, false otherwise.
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "()[]{}" Output: true
Example 3:
Input: s = "(]" Output: false
Recommended time and space complexity
You should aim for a solution with O(n) time complexity and O(n) space complexity, where n is the length of the input string.
Hint 1
A brute force approach would be to check each bracket against every other bracket in the string. This would be an O(n^2) time solution. Can you think of a more efficient approach?
Hint 2
Can you use a data structure that allows you to efficiently check if a bracket is closing and matches the last opened bracket?
Hint 3
We can use a stack to store open brackets. When we encounter a closing bracket, we check if it matches the last opened bracket in the stack.