Validate and Balance Parentheses with Wildcards

mediumSave

Dynamic ProgrammingGreedyStackString

Given a string s containing only three types of characters: '(', ')', and '*', write a function to check if the string is valid. The validity of a string is determined by these rules:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parentheses '(' must appear before their corresponding right parentheses ')'.
The character '*' can be treated as a single right parenthesis ')', a single left parenthesis '(', or an empty string.
An empty string is also considered valid.

Example 1

Input

[
  "()"
]

Output

true

Explanation. Standard balanced parentheses.

Example 2

Input

[
  "(*)"
]

Output

true

Explanation. The '*' can be treated as an empty string to balance '()'.

Example 3

Input

[
  "(*))"
]

Output

true

Explanation. The first '*' can be treated as an opening parenthesis '(', making it `(( ))`.

Example 4

Input

[
  "((("
]

Output

false

Explanation. Unmatched left parentheses.

Example 5

Input

[
  ")("
]

Output

false

Explanation. Right parenthesis appears before a corresponding left parenthesis.

Example 6

Input

[
  "((*)"
]

Output

false

Explanation. Even if '*' is treated as ')', we are left with an unmatched '('.

Example 7

Input

[
  "(*()*)",
  "**()**"
]

Output

true

Explanation. The first '*' can be '(', and the second '*' can be ')' to form `((()()))`.

Example 8

Input

[
  "***"
]

Output

true

Explanation. All '*' characters can be treated as empty strings.

Example 9

Input

[
  "*"
]

Output

true

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

Example 10

Input

[
  ")"
]

Output

false

Explanation. An unmatched right parenthesis.

Follow-up: Can you solve this problem with O(1) space complexity?

Constraints:

- The input string `s` will contain only '(', ')', and '*'. - The length of `s` will be between 1 and 100.

Views: 2