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

Recommended Time and Space Complexity

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)