# Parenthesis String

## Backtracking solution got TLE

`class Solution:    def checkValidString(self, s: str) -> bool:        self.valid = False        def valid_s(s):            if not s:return True            stack = []            for c in s:                if c==')':                    if not stack:return False                    if stack[-1]!='(':return False                    else:stack.pop()                else:                    stack.append(c)            #print(stack)            if not stack:return True            return False        def backtracking(s, hist):            #print(s, hist)            if not s:                if valid_s(hist):                    self.valid = True            else:                if not self.valid:                    if s !='*':                        backtracking(s[1:], hist+s)                    else:#'*' case                        backtracking(s[1:], hist+'(')                        if not self.valid:                            backtracking(s[1:], hist+')')                        if not self.valid:                            backtracking(s[1:], hist)        backtracking(s, "")        return self.valid`

## Backtraping with memo still get TLE

`from functools import lru_cacheclass Solution:    def checkValidString(self, s: str) -> bool:        def valid_s(s):            if not s:return True            stack = []            for c in s:                if c==')':                    if not stack:return False                    if stack[-1]!='(':return False                    else:stack.pop()                else:                    stack.append(c)            if not stack:return True            return False        @lru_cache(None)        def backtracking(s, hist):            if not s:return valid_s(hist)            if s !='*':                if backtracking(s[1:], hist+s):return True                else:return False            else:                if any(backtracking(s[1:], hist+cc) for cc in ['(', ')', '']):                    return True                return False        return backtracking(s, "")`

## DP got AC

`from functools import lru_cacheclass Solution:    def checkValidString(self, s: str) -> bool:        N = len(s)        @lru_cache(None)        def dp(i, j):            # it will touch one edge case whehter i is larger than j. It indicates that the substring is empty.            if i>j:return True            if i==j:return s[i]=='*'            # i < j case            if s[i] == ')':return False            if s[i] == '*':                if dp(i+1, j):return True               if s[i] == '(' or s[i]=='*':                candidates = [k for k in range(i+2,j) if s[k]!='(']                if s[i+1] != '(':                    if dp(i+1+1, j):return True                if s[j]!='(':                    if dp(i+1, j-1):return True                return any(dp(i+1,k-1) and dp(k+1,j)  for k in candidates)return dp(0, N-1)`

## An even better way

`class Solution:    def checkValidString(self, s: str) -> bool:        # initialize the number of '(' as 0        res = {0}        for c in s:            if c=='(':                res = {a+1 for a in res}            elif c==')':                res = {a-1 for a in res if a-1>=0}            else: #'*'                res = {a+k for a in res                            for k in [-1, 0 ,1]                           if a+k>=0}            if not res:return False        return 0 in res`

--

--