# Parenthesis String

Parenthesis String in most cases can be solved by using a stack efficiently. However, in some cases, we need advanced technologies such as DP to solve the problem.

## Backtracking solution got TLE

42 / 58 test cases passed. 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[0] !='*':                        backtracking(s[1:], hist+s[0])                    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[0] !='*':                if backtracking(s[1:], hist+s[0]):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

dp[i][j] means whether the s[i:j+1] is valid. We have some cases:

• if i>j: invalid. Valid if i >j. This case happens in the following description.
• if i==j, then dp[i][i] only valid when s[i]==’*’ as * can be treated as empty string.
• if j>i, we have three cases.
• 1) s[i] == ‘(’, it is valid if dp[i+1][k-1] and dp[k+1][j]for k in candidate_indexes, where candidate_indexes are indexes which can make s[k] == ‘)’ or ‘*’ (change ‘*’ into ‘)’ in this case).
• 2) s[i] ==’*’, it is valid if dp[i+1][j] or dp[i+1][k-1] and dp[k+1][j] if s[k]==’)’ or ‘*’
• 3) s[i]==’)’, invalid.

We figure all possible cases and in total, we have n² states. For each state, the worst case, we have to traverse about n subclasses, so the overall complexity is O(n³). n=100 in this problem, so it is doable.

Code is here

`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

if encounter ‘)’, num-=1

if encounter ‘*’, divide it into 3 cases:

• ‘’: num+=0
• ‘(’: num+=1
• ‘)’: num-=1

We should remove the negative value on the fly as it is not OK.

This algorithm has a complexity of O(n²)

`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`

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi