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

## 678. Valid Parenthesis String

## Backtracking solution got TLE

It got TLE as this algorithm has the complexity of O(3^k) k is the number of ‘*’ in the input string. The reason is the backtracking will try all possible ways.

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

We can change the code a little bit to let it return True or False and at the same time to add the memo for the code. However, it still got TLE.

`from functools import lru_cache`

class 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

The basic idea of DP is

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_cache

class 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

Counting the number of ‘(’. If we encounter a ‘(’, num+=1

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