Valid Parethesis

https://leetcode.com/problems/valid-parenthesis-string/

维护两个值cmin，cmax

cmin代表最少需要的"(" 来维持valid的状态

cmax代表做多可以用到的"("

这里需要注意的是cmin = max(cmin-1,0)

因为当当前char 是 ”）“的时候，如果你的cmin已经是负了而你的cmax还是正数（因为这里 cmax < 0 没有return False）说明其实你是使用了太多”*“ 去做 "(" 这时候所有")" 都已经被pair完了，你的原来本身的"("都得是负数才能valid，那么这时候你就应该让之前的"*" 变成empty string

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