Python, Greedy with Explanation


  • 0

    Let lo, hi respectively be the smallest and largest possible number of open left brackets after processing the current character c in the string. Every integer in this interval is possible to attain.

    If we see a '(', we know that we must have one extra left bracket, otherwise we could have one less. If we don't see a ')', we know we could have one extra left bracket, otherwise we must have one less.

    If at any point the maximum number of open left brackets is negative, then it is impossible to make a valid string. At the end, we want to know if it was possible to have exactly 0 open left brackets.

    def checkValidString(self, s):
        lo = hi = 0
        for c in s:
            lo += 1 if c == '(' else -1
            hi += 1 if c != ')' else -1
            if hi < 0: break
            lo = max(lo, 0)
    
        return lo == 0
    

  • 0
    This post is deleted!

Log in to reply
 

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