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: 1. Open brackets must be closed by the same type of brackets. 2. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.

Example 1

Input

[
  "()"
]

Output

true

Explanation. The brackets are balanced: each opening '(' has corresponding closing ')'.

Example 2

Input

[
  "()[]{}"
]

Output

true

Explanation. The brackets are balanced and in the correct order.

Example 3

Input

[
  "(]"
]

Output

false

Explanation. The round brackets are incorrectly closed with a square bracket.

Example 4

Input

[
  "([)]"
]

Output

false

Explanation. The brackets close out of order.

Example 5

Input

[
  "{[]}"
]

Output

true

Explanation. All types of brackets are balanced and close in the correct sequence.

Example 6

Input

[
  "["
]

Output

false

Explanation. There's an unclosed bracket.

Follow-up: Could you improve your algorithm to run with a time complexity of O(n)?

Constraints:

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

Views: 4