Balanced Brackets

mediumSave

StackString

Given a string containing only the characters (, ), {, }, [, and ], determine if the input string is valid. An input string is valid if:

Example 1

Input

[
  "()"
]

Output

true

Explanation. The parentheses are matched and closed in the correct order.

Example 2

Input

[
  "()[]{}"
]

Output

true

Explanation. All types of brackets are matched and closed correctly.

Example 3

Input

[
  "(]"
]

Output

false

Explanation. The parenthesis is closed with a bracket, which is incorrect.

Example 4

Input

[
  "([)]"
]

Output

false

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

Example 5

Input

[
  "{[]}"
]

Output

true

Explanation. All brackets are matched and closed correctly, in the proper nested order.

Follow-up: Could this problem be solved using another data structure? What would be the advantages and disadvantages?

Constraints:

1. The length of the input string is between 1 and 1000. 2. Only the characters `(`, `)`, `{`, `}`, `[`, and `]` are allowed in the input string.