Simple Python O(n) solution without DP or greedy


  • 1
    S

    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
    

    """


  • 1

    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
    

Log in to reply
 

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