678. Valid Parenthesis String

Medium

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules: 1. Any left parenthesis '(' must have a corresponding right parenthesis ')'. 2. Any right parenthesis ')' must have a corresponding left parenthesis '('. 3. Left parenthesis '(' must go before the corresponding right parenthesis ')'. 4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string. 5. An empty string is also valid.

😇 Solution

O(n)

class Solution:
    def checkValidString(self, s: str) -> bool:
        cmin = cmax = 0
        for i in s:
            cmax = cmax - 1 if i == ')' else cmax + 1
            cmin = cmin + 1 if i == '(' else max(cmin - 1, 0)
            if cmax < 0: return False
        return cmin == 0