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 open parentheses are matched by a closing parenthesis. An asterisk '' can be treated as a single right parenthesis ')' or a single left parenthesis '(' or it can be used to delete a character. The function should return true if the string is valid, and false otherwise.

Example 1

Input

[
  "(*)"
]

Output

true

Explanation. The asterisk can be treated as a left parenthesis to balance the right parenthesis.

Example 2

Input

[
  "(*))"
]

Output

true

Explanation. The asterisk can be treated as an empty string, making the input as `()` which is balanced.

Example 3

Input

[
  "("
]

Output

false

Explanation. There is no closing parenthesis or adequate asterisk to balance the open parenthesis.

Example 4

Input

[
  "(*)("
]

Output

false

Explanation. The asterisk can be treated as a right parenthesis, but there will still be an unmatched left parenthesis.

Example 5

Input

[
  "*"
]

Output

true

Explanation. The single asterisk can be treated as an empty string or any single parenthesis; thus, it is trivially balanced.

Follow-up: Could enhancing the algorithm to handle more types of brackets ([, {, etc.) be a useful extension?

Constraints:

The input string will only contain '(', ')', and '*'.

Views: 2