Balanced Brackets

mediumSave

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 closed bracket has a corresponding matching open bracket of the same type.

Example 1

Input

[
  "()"
]

Output

true

Explanation. The parentheses are balanced and appear in the correct order.

Example 2

Input

[
  "()[]{}"
]

Output

true

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

Example 3

Input

[
  "(]"
]

Output

false

Explanation. The parentheses are not balanced because ']'' does not properly close '('.

Example 4

Input

[
  "([)]"
]

Output

false

Explanation. The brackets are not in the correct order even though each type starts and ends correctly.

Example 5

Input

[
  "{[]}"
]

Output

true

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

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

Constraints:

1. The length of the input string is between 1 and 1000. 2. The input string consists only of the characters '(', ')', '{', '}', '[' and ']'.