Balanced Parentheses

Dynamic ProgrammingGreedyStackString

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string. An input string may contain any number of characters, and it must be processed to determine if it is balanced based on the aforementioned rules.

Example 1

Input

[
  "(*)"
]

Output

True

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

Example 2

Input

[
  "(*)("
]

Output

False

Explanation. There is an unmatched left parenthesis that doesn't have a corresponding closing parenthesis.

Example 3

Input

[
  "(****))"
]

Output

True

Explanation. Two of the '*' characters can be treated as two left parentheses and two can be empty making the parentheses balanced.

Example 4

Input

[
  "((*)"
]

Output

True

Explanation. The '*' may be treated as a ')' to balance the parentheses.

Example 5

Input

[
  "*())"
]

Output

True

Explanation. The first '*' can be treated as '(', balancing the parentheses.

Example 6

Input

[
  ")*("
]

Output

null

Explanation. Parentheses are wrongly ordered even if '*' treats as a parenthesis.

Follow-up: Could you solve this problem in linear time complexity with constant space?

Constraints:

The length of the string s will be in the range [1, 100].

Views: 1