Day 16 - Valid Parenthesis String

Solution.py

# https://leetcode.com/explore/featured/card/30-day-leetcoding-challenge/530/week-3/3301/

class Solution:
    def checkValidString(self, s: str) -> bool:
        dp = {}
        return self.isValid(s, 0, 0, dp)
    
    def isValid(self, s: str, i: int, c: int, dp: dict) -> bool:
        if (i, c) in dp:
            return dp[i, c]
        
        if i == len(s):
            if c == 0:
                return True
            else:
                return False
            
        if s[i] == '*':
            dp[i, c] = self.isValid(s, i + 1, c, dp) or \
                       self.isValid(s, i + 1, c + 1, dp) or \
                       (self.isValid(s, i + 1, c - 1, dp) if c > 0 else False)
        
        elif s[i] == '(':
            dp[i, c] = self.isValid(s, i + 1, c + 1, dp)
        elif s[i] == ')':
            if c == 0:
                dp[i, c] = False
            else:
                dp[i, c] = self.isValid(s, i + 1, c - 1, dp)
        
        return dp[i, c]