from collections import Counter
class Solution(object):
    def dfs(self, s, pos, stack):
        if stack + self.min_possible_opening[-1] - self.min_possible_opening[pos] > self.max_possible_closing[-1] - self.max_possible_closing[pos]:
            return False
        if stack + self.max_possible_opening[-1] - self.max_possible_opening[pos] < self.min_possible_closing[-1] - self.min_possible_closing[pos]:
            return False
        if pos == len(s):
            return not stack
        if s[pos] == '(':
            stack += 1
            if self.dfs(s, pos + 1, stack):
                return True
            stack -= 1
        elif s[pos] == ')':
            if not stack:
                return False
            else:
                stack -= 1
                if self.dfs(s, pos + 1, stack):
                    return True
                stack += 1
        else:
            if stack: # treat as ')'
                stack -= 1
                if self.dfs(s, pos + 1, stack):
                    return True
                stack += 1
            # treat as '('
            stack += 1
            if self.dfs(s, pos + 1, stack):
                return True
            stack -= 1

            # treat as ''
            if self.dfs(s, pos + 1, stack):
                return True
        return False

    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        c = Counter(s)
        mpo, mpc = c['('] + c['*'], c[')'] + c['*']

        self.max_possible_opening = [0]
        self.min_possible_opening = [0]
        self.max_possible_closing = [0]
        self.min_possible_closing = [0]
        for c in s:
            self.min_possible_opening.append(self.min_possible_opening[-1] + (c == '('))
            self.max_possible_opening.append(self.max_possible_opening[-1] + (c != ')'))
            self.min_possible_closing.append(self.min_possible_closing[-1] + (c == ')'))
            self.max_possible_closing.append(self.max_possible_closing[-1] + (c != '('))

        return self.dfs(s, 0, 0)

class Solution(object):

    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        lowest, highest = 0, 0
        for c in s:
            if c == '(':
                lowest += 1
                highest += 1
            elif c == ')':
                if lowest > 0:
                    lowest -= 1
                highest -= 1
                if highest < 0:
                    return False
            else:
                if lowest > 0:
                    lowest -= 1
                highest += 1
        return lowest == 0

Add py solution for 678. Valid Parenthesis String
Add py solution for 678. Valid Parenthesis String

678. Valid Parenthesis String: https://leetcode.com/problems/valid-parenthesis-string/

Approach2:
    Maintain the lowest/highest possible stack size and check if one of
    them is invalid
    O(n) time, O(1) size
