Balanced Brackets

mediumSave

StackString

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid and all the brackets are balanced. An input string is balanced if:\n1. Open brackets must be closed by the same type of brackets.\n2. Open brackets must be closed in the correct order.\n3. An empty string is considered balanced.

Example 1

Input

[
  "()"
]

Output

true

Explanation. Single type of bracket pairs, properly closed.

Example 2

Input

[
  "()[]{}"
]

Output

true

Explanation. Multiple types of bracket pairs, all appropriately closed.

Example 3

Input

[
  "(]"
]

Output

false

Explanation. Mismatched bracket types.

Example 4

Input

[
  "([)]"
]

Output

false

Explanation. Brackets closed in the incorrect order.

Example 5

Input

[
  "{[]}"
]

Output

true

Explanation. Nested brackets properly closed.

Follow-up: Is there a way to optimize the solution using a different data structure?

Constraints:

1. The string may contain any of the characters: '(', ')', '{', '}', '[' and ']' only.\n2. The length of the string is at most 10^4.

Views: 2