Solutions

# 2 stacks (1 for '(' and 1 for '*'), greedy (counting min and max possible open parentheses), DFS recursive, top-down DP, bottom-up DP
# greedy

# Stack - O(n) time, O(n) space
def checkValidString(s: str) -> bool:
    stackpars = []
    stackstar = []

    for i, c in enumerate(s):

        if c == '(':
            stackpars.append(i)
        elif c == '*':
            stackstar.append(i)
        elif c == ')':

            if not stackpars and not stackstar:
                return False
            
            if stackpars:
                stackpars.pop()
            elif stackstar:
                stackstar.pop()
    
    while stackstar and stackpars:
        # NB: any remaining ( should be matched by a * appearing AFTER it
        if stackpars.pop() > stackstar.pop():
            return False

    return not stackpars


# Greedy - O(n) time, O(1) space
def checkValidString(s: str) -> bool:
    # min and max possible of open unmatched parenthesis at any point
    openLeftMin = 0
    openLeftMax = 0

    for c in s:
        if c == '(':
            openLeftMax += 1
            openLeftMin += 1
        elif c == ')':
            openLeftMax -= 1
            openLeftMin -= 1
        else: # '*'
            openLeftMin -= 1 # )
            openLeftMax += 1 # (

        if openLeftMax < 0: # too many closing parens
            return False
        if openLeftMin < 0:
            openLeftMin = 0
    
    return openLeftMin == 0

# DFS recursive - O(3^n) time, O(n) space
def checkValidString(s: str) -> bool:

    def dfs(i: int, opened: int) -> bool:
        if opened < 0:
            return False 
        if i == len(s):
            return opened == 0

        if s[i] == '(':
            return dfs(i+1, opened+1)
        elif s[i] == ')':
            return dfs(i+1, opened-1)
        else: # s[i] == '*'
            res = False
            res |= dfs(i+1, opened)
            res |= dfs(i+1, opened-1)
            res |= dfs(i+1, opened+1)
            return res

    return dfs(0, 0)


# Top-down DP - O(n^2) time, O(n^2) space
# n^2 states (opened and i both range 0->n), each computed once
def checkValidString(s: str) -> bool:
    dp = {}

    def dfs(i: int, opened: int) -> bool:
        if opened < 0:
            return False 
        elif i == len(s):
            return opened == 0
        elif (i,opened) in dp:
            return dp[(i,opened)]

        if s[i] == '(':
            res = dfs(i+1, opened+1)
        elif s[i] == ')':
            res = dfs(i+1, opened-1)
        else: # s[i] == '*'
            res = False
            res |= dfs(i+1, opened)
            res |= dfs(i+1, opened-1)
            res |= dfs(i+1, opened+1)
        dp[(i,opened)] = res
        return res

    return dfs(0, 0)


# Bottom-up DP - O(n^2) time, O(n^2) space
def checkValidString(s: str) -> bool:
    n = len(s)
    # dp[i][opened]
    dp = [[False] * (n+1) for _ in range(n+1)]
    # Base case: last char and 0 opened
    dp[n][0] = True

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

    return dp[0][0]