Balanced Parentheses Checker

StackString

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: 1. Open brackets must be closed by the same type of brackets. 2. Open brackets must be closed in the correct order. Note that an empty string is also considered valid.

Example 1

Input

[
  "()"
]

Output

true

Explanation. The parentheses are balanced as each opening parenthesis '(' is closed by a matching closing parenthesis ')'.

Example 2

Input

[
  "()[]{}"
]

Output

true

Explanation. All types of brackets are balanced and closed in the correct order.

Example 3

Input

[
  "(]"
]

Output

false

Explanation. The parenthesis '(' is incorrectly closed with a different type of bracket ']'.

Example 4

Input

[
  "([)]"
]

Output

false

Explanation. The brackets are not closed in the correct order.

Example 5

Input

[
  "{[]}"
]

Output

true

Explanation. All brackets are balanced and each open bracket is followed by its matching close bracket in the correct order.

Example 6

Input

[
  ""
]

Output

true

Explanation. An empty string is considered valid as there are no unmatched brackets to make it invalid.

Follow-up: Can you solve this problem using a data structure or method that optimizes space complexity?

Constraints:

The input string will only contain the characters '(', ')', '{', '}', '[' and ']'.

Views: 3