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

Example 1

Input

[
  "()"
]

Output

true

Explanation. The string consists of one pair of parentheses which matches correctly.

Example 2

Input

[
  "()[]{}"
]

Output

true

Explanation. Each type of open bracket has a corresponding close bracket in the correct order.

Example 3

Input

[
  "(]"
]

Output

false

Explanation. The parenthesis is incorrectly closed by a square bracket.

Example 4

Input

[
  "([)]"
]

Output

false

Explanation. The brackets close in the wrong order.

Example 5

Input

[
  "{[]}"
]

Output

true

Explanation. All open brackets are closed by their corresponding brackets in the correct order.

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

Constraints:

1. The string will only contain the characters '(', ')', '{', '}', '[' and ']'.\n2. The length of the string is between 1 and 10,000.

Views: 3