Valid Parenthesis String

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 "".

• 1 ≤ s.length ≤ 100

Examples

1. Recursion / DFS

This problem asks whether a string containing '(', ')', and '*' can be interpreted as a valid parentheses string.

The tricky part is '*', because it can represent:

• '('
• ')'
• an empty string

Using recursion, we try all valid interpretations of the string while keeping track of how many opening parentheses are currently unmatched. The recursive function answers: "Is it possible to make the substring starting at index i valid, given that we currently have open unmatched '('?"

Important rules:

• The number of open parentheses (open) should never be negative.
• At the end of the string, all open parentheses must be closed (open == 0).

class Solution:
    def checkValidString(self, s: str) -> bool:

        def dfs(i, open):
            if open < 0:
                return False
            if i == len(s):
                return open == 0

            if s[i] == '(':
                return dfs(i + 1, open + 1)
            elif s[i] == ')':
                return dfs(i + 1, open - 1)
            else:
                return (dfs(i + 1, open) or
                        dfs(i + 1, open + 1) or
                        dfs(i + 1, open - 1))
        return dfs(0, 0)

Time Complexity: O(3ⁿ) because each '*' branches into 3 possibilities.
Space Complexity: O(n) for the recursion stack depth.

2. Dynamic Programming

Top-Down Memoization

A brute-force recursion tries all possibilities, but it repeats the same work for the same positions and open counts. To avoid that, we use top-down dynamic programming (memoization).

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)
        memo = [[None] * (n + 1) for _ in range(n + 1)]

        def dfs(i, open):
            if open < 0:
                return False
            if i == n:
                return open == 0
            if memo[i][open] is not None:
                return memo[i][open]

            if s[i] == '(':
                result = dfs(i + 1, open + 1)
            elif s[i] == ')':
                result = dfs(i + 1, open - 1)
            else:
                result = (dfs(i + 1, open) or
                          dfs(i + 1, open + 1) or
                          dfs(i + 1, open - 1))

            memo[i][open] = result
            return result

        return dfs(0, 0)

Bottom-Up DP

In bottom-up DP, we build answers for smaller suffixes first. We define dp[i][open] as whether it is possible to make s[i:] valid if we currently have open unmatched '('.

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)
        dp = [[False] * (n + 1) for _ in range(n + 1)]
        dp[n][0] = True

        for i in range(n - 1, -1, -1):
            for open in range(n):
                res = False
                if s[i] == '*':
                    res |= dp[i + 1][open + 1]
                    if open > 0:
                        res |= dp[i + 1][open - 1]
                    res |= dp[i + 1][open]
                else:
                    if s[i] == '(':
                        res |= dp[i + 1][open + 1]
                    elif open > 0:
                        res |= dp[i + 1][open - 1]
                dp[i][open] = res

        return dp[0][0]

Space Optimized DP

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(n - 1, -1, -1):
            new_dp = [False] * (n + 1)
            for open in range(n):
                if s[i] == '*':
                    new_dp[open] = (dp[open + 1] or
                                    (open > 0 and dp[open - 1]) or
                                    dp[open])
                elif s[i] == '(':
                    new_dp[open] = dp[open + 1]
                elif open > 0:
                    new_dp[open] = dp[open - 1]
            dp = new_dp

        return dp[0]

Time Complexity: O(n²)
Space Complexity: O(n)

3. Two Stacks — O(n)

The key idea is to keep track of indices of unmatched '(' and indices of '*'. Use '*' as a backup when we encounter an unmatched ')'. At the end, we must also ensure that any remaining '(' can be matched with a '*' that appears after it.

class Solution:
    def checkValidString(self, s: str) -> bool:
        left = []
        star = []
        for i, ch in enumerate(s):
            if ch == '(':
                left.append(i)
            elif ch == '*':
                star.append(i)
            else:
                if not left and not star:
                    return False
                if left:
                    left.pop()
                else:
                    star.pop()

        while left and star:
            if left.pop() > star.pop():
                return False
        return not left

Time Complexity: O(n)
Space Complexity: O(n)

4. Greedy Range Tracking — O(n)

Instead of trying all possibilities or using stacks, we can solve this greedily by tracking a range of possible unmatched '(' counts. At any point, we don't need the exact number of open parentheses, we only need to know the minimum and maximum number of '(' that could be open.

Why this works:

• '(' always increases the number of open parentheses.
• ')' always decreases it.
• '*' is flexible and can: decrease open count (act as ')'), increase open count (act as '('), or keep it unchanged (act as empty).

So we maintain leftMin (minimum possible number of unmatched '(') and leftMax (maximum possible number of unmatched '('). If at any point the maximum possible opens becomes negative, the string is invalid. At the end, if the minimum possible opens is zero, the string can be valid.

Common Pitfalls

Forgetting That Wildcards Have Three Options

A common mistake is treating '*' as only representing '(' or ')'. Remember that '*' can also represent an empty string. This third option is crucial for cases like "(*)" where the '*' should be treated as empty to form a valid string.

Not Checking for Negative Open Count

When processing ')' or treating '*' as ')', you must ensure the open parenthesis count never goes negative. A negative count means there are more closing parentheses than opening ones at that point, which is invalid regardless of what comes later. Always check open ≥ 0 before proceeding.