Python easy understand solution


  • 3

    The number of open parenthesis is in a range [cmin, cmax]
    cmax counts the maximum open parenthesis, which means the maximum number of unbalanced '(' that COULD be paired.
    cmin counts the minimum open parenthesis, which means the number of unbalanced '(' that MUST be paired.

    The string is valid for 2 condition:

    1. cmax will never be negative.
    2. cmin is 0 at the end.
    def checkValidString(self, s):
            cmin = cmax = 0
            for i in s:
                if i == '(':
                    cmax += 1
                    cmin += 1
                if i == ')':
                    cmax -= 1
                    cmin = max(cmin - 1, 0)
                if i == '*':
                    cmax += 1
                    cmin = max(cmin - 1, 0)
                if cmax < 0:
                    return False
            return cmin == 0
    

    or shorter:

    def checkValidString(self, s):
            cmin = cmax = 0
            for i in s:
                cmax = cmax-1 if i==")" else cmax+1
                cmin = cmin+1 if i=='(' else max(cmin - 1, 0) 
                if cmax < 0: return False
            return cmin == 0
    

    Edited after vonzcy's suggestion.


  • 0
    T

    @lee215 why cant cmin be less than 0?


  • 0
    V

    @topcoder4309

    cmin means the number of unbalanced '(' that MUST be paired and cmax means the maximum number of unbalanced '(' that COULD be paired. If you don't have enough MUST, supply with COULD.


  • 1
    J

    @topcoder4309
    cmax considers each '*' as '(', which should never be negative
    cmin considers each '*' as ')' as much as possible (treat it as empty string if cmin<0 -- "max(cmin-1, 0)").
    In the end, cmin should be 0. If it's larger than 0, it means even if we consider every '*' as ')', there is still some '(' left.


Log in to reply
 

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