Balance The Brackets

mediumSave

StackString

Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid based on the balance of the brackets. An input string is valid if:\n\n1. Open brackets must be closed by the same type of brackets.\n2. Open brackets must be closed in the correct order.

Example 1

Input

[
  "()"
]

Output

true

Explanation. The string contains matching parenthesis, which makes it balanced.

Example 2

Input

[
  "()[]{}"
]

Output

true

Explanation. Each type of bracket is balanced and correctly nested.

Example 3

Input

[
  "(]"
]

Output

false

Explanation. There is a mismatched parenthesis.

Example 4

Input

[
  "([)]"
]

Output

false

Explanation. The brackets are not properly nested.

Example 5

Input

[
  "{[]}"
]

Output

true

Explanation. All types of brackets are balanced and properly nested.

Example 6

Input

[
  "["
]

Output

false

Explanation. An unmatched open bracket remains.

Follow-up: Can you optimize your solution to run in O(n) time complexity?

Constraints:

1. The string may be empty.\n2. The length of the string will not exceed 1000.

Views: 3