Balanced Parentheses

StackString

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A valid string is defined as follows: \n1. Open brackets must be closed by the same type of brackets. \n2. Open brackets must be closed in the correct order. \n3. An empty string is also considered valid.

Example 1

Input

[
  "()"
]

Output

true

Explanation. The open parenthesis '(' is closed by the same type of bracket ')'. It satisfies all the conditions for a string to be valid.

Example 2

Input

[
  "()[]{}"
]

Output

true

Explanation. Each open bracket has a corresponding matching closing bracket.

Example 3

Input

[
  "(]"
]

Output

false

Explanation. The open parenthesis '(' is closed by a different type of bracket ']'.

Example 4

Input

[
  "([)]"
]

Output

false

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

Example 5

Input

[
  "{[]}"
]

Output

true

Explanation. All open brackets are closed by the same type of brackets and in the correct order.

Example 6

Input

[
  ""
]

Output

true

Explanation. An empty string is considered valid.

Follow-up: Can you solve it without using additional data structures like stacks or queues?

Constraints:

1. The string may include characters: '(', ')', '{', '}', '[' and ']'. \n2. The length of the string can be from 0 to 10,000.

Views: 3