Python short & simple O(n) time, O(1) space solution


  • 0
    Y

    First from left to right, replace all the * with ( to check if it can be valid.
    Then from right to left, replace all the * with ) to check if it can be valid.

    class Solution:
        def checkValidString(self, s):
            """
            :type s: str
            :rtype: bool
            """
            return self.checkHelp('(', ')', s) and self.checkHelp(')', '(', reversed(s))
            
        def checkHelp(self, first, second, s):
            count = 0
            for c in s:
                if c == first or c == '*':
                    count += 1
                elif c == second:
                    count -= 1
                    if count < 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.