# Simple Python O(n) solution without DP or greedy

• The idea is, how we can test if such string is valid or not? So we always go from one end to another end and remove the part that already valid.

So here the algorithm always record how many stars are available to be used as a parenthesis. So if we miss parenthesis, we use a backup *. If there is no * available, we return false. Noticed that we need either do from both directions or keep the parenthesis separately.

"""

``````def checkValidString(self, s):

star_count = 0
par_count = 0
for cha in s:
if cha == "(":
par_count += 1
if cha == ")":
par_count -= 1
if cha == "*":
star_count += 1
if par_count < 0:
if par_count + star_count < 0:
return False
else:
star_count = par_count + star_count
par_count = 0

if par_count == 0 or par_count - star_count <= 0:
pos =  True
else:
pos =  False

star_count = 0
par_count = 0
for cha in s[::-1]:
if cha == "(":
par_count -= 1
if cha == ")":
par_count += 1
if cha == "*":
star_count += 1
if par_count < 0:
if par_count + star_count < 0:
return False
else:
star_count = par_count + star_count
par_count = 0

if par_count == 0 or par_count - star_count <= 0:
rev =  True
else:
rev =  False

if pos and rev:
return True
else:
return False
``````

"""

• Has been posted on another thread but I think it's more relevant here, exactly the same idea but clear a little bit:

``````    def checkValidString(self, s):
cus, cur = 0, 0
for i in range(len(s)):
cus += {'(': 1, ')': -1, '*': 1}[s[i]]
cur += {'(': -1, ')': 1, '*': 1}[s[-i-1]]
if cus < 0  or cur < 0:
return False
return True
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.