合法的括号字符串

class Solution:
    def isValidString(self, s: str) -> bool:
        low, high = 0, 0  # 维护左括号数量的最小、最大可能值
        for c in s:
            if c == '(':
                low += 1
                high += 1
            elif c == ')':
                if low > 0:  # 尽量消耗左括号，减少最小可能
                    low -= 1
                high -= 1  # 右括号必须匹配，最大可能减少
            else:  # c == '*'，三种情况取最优
                if low > 0:  # * 当右括号，减少最小可能
                    low -= 1
                high += 1  # * 当左括号，增加最大可能
            if high < 0:  # 右括号过多，直接不合法
                return False
        return low <= 0

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return bool布尔型
#
class Solution:
    def isValidString(self , s: str) -> bool:
        # write code here
        stack=[]
        if(len(s)==0):
            return True
        count=0
        for j in range(len(s)):
            if(s[j]=='('):
                count+=1
            elif(s[j]==')'):
                count-=1
        if(count>=0):
            for i in range(len(s)):
                if(s[i]=='('):
                    stack.append(s[i])
                if(s[i]==')'):
                    try:
                        stack.pop()
                    except:return False
                if(s[i]=='*' and len(stack)!=0 and count!=0):
                    stack.pop()
                    count-=1
        if(count<0):
            for i in range(len(s)):
                if(s[i]=='*'and count!=0):
                    stack.append(s[i])
                    count+=1
                if(s[i]=='('):
                    stack.append(s[i])
                if(s[i]==')'):
                    try:
                        stack.pop()
                    except:return False
        if(len(stack)==0):
            return True
        else:return False

class Solution:
    def isValidString(self , s: str) -> bool:
        l = []
        star = []
        for i in range(len(s)):
            if s[i] == '(':
                l.append(i)
            elif s[i] == '*':
                star.append(i)
            elif s[i] == ')':
                if l:
                    l.pop()
                elif star:
                    star.pop()
                else:
                    return False
        if len(l) > len(star):
            return False
        i = j = 0
        while l and j < len(star):
            if l[i] < star[j]:
                l.pop(i)
                star.pop(j)
            else:
                j += 1
        if l == []:
            return True
        else:
            return False

class Solution:
    def isValidString(self , s: str) -> bool:
        if s[0] == ')':
            return False
        dic = {')': '(', '*': '*'}
        res,res2,res3 = [],[],[]
        start = 0
        for i in range(len(s)):
            if s[i] not in dic.keys():
                res.append(s[i])
                res2.append(i)
            else:
                if s[i] == "*":
                    start += 1
                    res3.append(i)
                elif len(res) > 0:
                    res.pop()
                    res2.pop()
        if len(res) == 0:
            return True
        elif len(res) <= start:
            while res2:
                if res2[-1] > res3[-1]:
                    return False
                else:
                    res2.pop()
                    res3.pop()
            return True
        else:
            return False