678. Valid Parenthesis String (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        # greedy solution
        low = high = 0
        for c in s:
            if c == "(":
                low += 1
                high += 1
            elif c == ")":
                low = max(low - 1, 0)
                high -= 1
            else:
                low = max(low - 1, 0)
                high += 1
            if high < 0:
                return False
        return low == 0
        
        # stack solution
        stars, stack = [], []
        for i, c in enumerate(s):
            if c == "*":
                stars.append(i)
            elif c == "(":
                stack.append(i)
            else:
                if stack:
                    stack.pop()
                else:
                    if stars:
                        stars.pop()
                    else:
                        return False
        if len(stack) > len(stars):
            return False
        while stack:
            if stack.pop() > stars.pop():
                return False
        return True