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

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

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

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