Parenthesis String

678. Valid 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[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

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

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store