LeetCode 678 Valid Parenthesis string

LeetCode 678

这个题目看起来不难，但是实际上我觉得还是挺容易错的。

看到parenthesis的validation题目，自然想到的是stack，如果没有 * ，每次看到（就push进去，看到）就pop，最后是空就对了。

但是有了*，可以任意替换，一种方法就是*单独存一个stack，遇到）的时候，先pop （的stack，没有的话pop *的stack。

方法上基本上正确，第一遍写的时候就错了，漏掉了 这样的case： *（（）

*在这种情况下其实没有啥左右，不能转为）来match。

重新整理了代码变成这样：

def checkValidString2(self, s: str) -> bool:
        stack = []
        star_stack = []
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            elif c == '*':
                star_stack.append(i)
            else:
                if not stack and not star_stack:
                    return False
                if stack:
                    stack.pop()
                else:
                    star_stack.pop()

        while stack and star_stack:
            if stack.pop()>star_stack.pop():
                return False

        return not stack
           

当然还有一个思路就是，从前向后检查一遍，然后在从后向前检查一遍，这个也是可以的。

def checkValidStringSlow(self, s: str) -> bool:
        if s == None or len(s) == 0: return True

        def check(s, p)-> bool:
            pstack = list()
            startCount = 0
            
            for c in s:
                if c == p:
                    pstack.append(c)
                elif c == '*':
                    startCount +=1
                else:
                    if pstack:
                        pstack.pop()
                    elif startCount > 0:
                        startCount -=1
                    else:
                        return False
            
            return len(pstack) <= startCount

        return check(s, '(') and check(s[::-1], ')')
           

根据这个想法，再进行一次优化，把栈去掉，其实我们只要计数就够了，其实并不一定要存下来。

def checkValidString(self, s: str) -> bool:
        if s == None or len(s) == 0: return True

        ls = len(s) -1
        openCount = 0
        closeCount = 0
        for i, c in enumerate(s):
            if c != ')': 
                openCount +=1
            else: 
                openCount -=1

            if s[ls-i] != '(':
                closeCount +=1
            else:
                closeCount -=1

            if openCount < 0 or closeCount < 0:
                return False
        
        return True