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