Balanced Parentheses

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.

Example 1

Input

[
  "()"
]

Output

true

Explanation. The only pair of parentheses are matching and well-formed.

Example 2

Input

[
  "()[]{}"
]

Output

true

Explanation. All types of parentheses are matching and correctly ordered.

Example 3

Input

[
  "(]"
]

Output

false

Explanation. The parenthesis ')' is not correctly matched with its open counterpart.

Example 4

Input

[
  "([)]"
]

Output

false

Explanation. The parentheses are not correctly ordered.

Example 5

Input

[
  "{[]}"
]

Output

true

Explanation. All brackets are correctly matched and nested.

Follow-up: How would you optimize your solution for a string with nested parentheses structures of varying lengths and types?

Constraints:

1. The string may include characters that are not one of the six parenthesis characters mentioned. 2. The length of the input string will be at least 1.

Views: 4