678. 有效的括号字符串

栈 贪心

方法一栈

括号问题一般采用栈来解决，建立一个左括号栈和一个星号栈，从左到右遍历，如果遇到左括号或者星号则直接入栈，遇到右括号，优先找左括号栈，如果左括号么有则找星号栈。当遍历完一边之后，如果左括号栈没有元素那么刚好，否则就要试着用星号作为右括号和左括号匹配。可以匹配的条件是星号的的下标要大于左括号的下标。

参考代码

class Solution:
    def checkValidString(self, s: str) -> bool:
        left, star = [], []
        for i in range(0,len(s)):
            c = s[i]
            if c == '(':
                left.append(i)
            elif c == '*':
                star.append(i)
            else:
                if left:
                    left.pop()
                elif star:
                    star.pop()
                else: 
                    return False
        while left:
            c = left.pop()
            if star and star.pop() > c:
                pass
            else:
                return False
        return True

复杂度分析

时间复杂度 O(n)
空间复杂度 O(n)

方法二贪心

从左到右遍历一边，确保搜有的右括号都要匹配上。从右到左再遍历一边确保所有左括号都匹配上，左右括号都匹配上了那么就是匹配上了，否则就是不匹配

参考代码

class Solution:
    def checkValidString(self, s: str) -> bool:
        left, star = 0,0
        for c in s:
            if c == '(':
                left+= 1
            elif c == '*':
                star += 1
            elif left:
                left -= 1
            elif star:
                star -= 1
            else: return False
        right, star = 0,0
        for c in reversed(s):
            if c == ')':
                right += 1
            elif c == '*':
                star += 1
            elif right:
                right -= 1
            elif star:
                star -= 1
            else: return False
        return True

复杂度分析

时间复杂度 O(n)
空间复杂度 O(1)