Balanced Parentheses

Dynamic ProgrammingGreedyStackString

Given a string containing only three types of characters: '(', ')' and '', write a function to check whether this string is valid. The string is valid if all the open parentheses are closed by the corresponding closing parenthesis and vice versa, and all '' can be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.

Example 1

Input

[
  "()"
]

Output

true

Explanation. The parentheses are balanced.

Example 2

Input

[
  "(*)"
]

Output

true

Explanation. The '*' can be treated as an empty string.

Example 3

Input

[
  "(*))"
]

Output

true

Explanation. The '*' can be treated as '('.

Example 4

Input

[
  "("
]

Output

false

Explanation. There isn't a corresponding closing parenthesis.

Example 5

Input

[
  "*("
]

Output

false

Explanation. '*' cannot be transformed to balance the parentheses.

Follow-up: Could you solve it without using extra space for another data structure (e.g., without explicitly using a stack or recursively calling a function)?

Constraints:

1. The string size will be in the range [1, 100].\n2. The string will contain only '(', ')', and '*' characters.

Views: 3