Valid Parenthesis String

Problem Statement

You are given a string s which contains only three types of characters: '(', ')' and '*'.

Return true if s is valid, otherwise return false.

A string is valid if it follows all of the following rules:

  • Every left parenthesis '(' must have a corresponding right parenthesis ')'.
  • Every right parenthesis ')' must have a corresponding left parenthesis '('.
  • Left parenthesis '(' must go before the corresponding right parenthesis ')'.
  • A '*' could be treated as a right parenthesis ')' character or a left parenthesis '(' character, or as an empty string "".

Example 1:

# Example in Python
s = "((**)"
# Returns: True

Explanation: One of the '*' could be a ')' and the other could be an empty string.

Example 2:

# Example in Python
s = "(((*)"
# Returns: False

Explanation: The string is not valid because there is an extra '(' at the beginning, regardless of the extra '*'.

Constraints:

  • 1 <= s.length <= 100

Aim for O(n) time and O(1) space for optimal solutions.

Hint 1

Consider how ’*’ can act as ’(’ or ’)’ or an empty string.

Hint 2

Think about using stacks or dynamic programming to keep track of parenthesis counts.

Hint 3

A greedy approach might simplify the problem by tracking the possible range of open parentheses.

Solution

Recursion

def check_valid_string_recursive(s: str) -> bool:
def dfs(i: int, open_count: int) -> bool:
if open_count < 0:
return False
if i == len(s):
return open_count == 0
if s[i] == '(':
return dfs(i + 1, open_count + 1)
elif s[i] == ')':
return dfs(i + 1, open_count - 1)
else:
return (dfs(i + 1, open_count) or
dfs(i + 1, open_count + 1) or
dfs(i + 1, open_count - 1))
return dfs(0, 0)

Time complexity: O(3 ^ n) Space complexity: O(n)