Valid Parenthesis String

LeetCode 678

class Solution:
    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        """
        
        計算當下"最佳解"和"最糟解" 如果【連最佳解都失敗了】那就是失敗
        1. 當遇到 "(" : 最糟解 + 1
        
        2. 當遇到 "不是 )" -> 有可能遇到的是 "( 或 *" 最佳解 + 1    
        3. 當遇到 ")" : 最佳解 - 1
        
        4. 當遇到 "不是 (": 最糟解 - 1 
        
        5. "*)" lo = -1 hi = 1 給定 lo = max(lo, 0)
        
        """
        lo = hi = 0
        for c in s:
             
            if c == '(':
                lo += 1
            else:
                lo -= 1
                        
            if c = ')':
                hi -= 1
            else:
                hi += 1
            if hi < 0: 
                break
                         
            lo = max(lo, 0)

        return lo == 0