Balance The Brackets
easySave
StackString
Given a string 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
[ "([)]" ]
Output
false
Explanation. The brackets are not closed in the correct order.
Example 2
Input
[ "()" ]
Output
true
Explanation. The brackets are correctly paired and ordered.
Example 3
Input
[ "()[]{}" ]
Output
true
Explanation. All types of brackets are correctly paired and ordered.
Example 4
Input
[ "(]" ]
Output
false
Explanation. The round bracket is incorrectly closed by a square bracket.
Example 5
Input
[ "{[]}" ]
Output
true
Explanation. All types of brackets are correctly paired and nested.
Example 6
Input
[ "[" ]
Output
false
Explanation. There is no corresponding closing bracket.
Follow-up: Can you optimize your solution to run in O(n) time complexity?
Constraints:
The input string will only contain the characters '(', ')', '{', '}', '[' and ']', and can be empty.
- Views
- 1