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 one type of bracket and they are correctly balanced.

Example 2

Input

[
  "()[]{}"
]

Output

true

Explanation. Each type of bracket is correctly matched and closed in the proper order.

Example 3

Input

[
  "(]"
]

Output

false

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

Example 4

Input

[
  "([)]"
]

Output

false

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

Example 5

Input

[
  "{[]}"
]

Output

true

Explanation. All types of brackets are matched and closed correctly.

Follow-up: How would you optimize your solution for a string that primarily consists of non-bracket characters?

Constraints:

1. The input string may contain characters other than the six bracket characters mentioned. These should not affect the validity of the string.\n2. The length of the input string will be at least 1 and at most 10000 characters.

Views: 2