Balanced Parentheses

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 contains matching pair of parenthesis which are correctly ordered.

Example 2

Input

[
  "()[]{}"
]

Output

true

Explanation. The string contains matching pairs of parenthesis which are correctly ordered.

Example 3

Input

[
  "(]"
]

Output

false

Explanation. There is a mismatch between types of brackets.

Example 4

Input

[
  "([)]"
]

Output

false

Explanation. The brackets are correctly matched but are out of order.

Example 5

Input

[
  "{[]}"
]

Output

true

Explanation. All brackets are matched and in the correct order.

Follow-up: Can you solve this problem without using extra space for another data structure, such as a stack?

Constraints:

1. The length of the input string is at least 1 and at most 10000.\n2. Only the characters '(', ')', '{', '}', '[' and ']' will appear in the input string.

Views: 4