题解 | #合法的括号字符串#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return bool布尔型
#
class Solution:
    
    def isValidString(self , s: str) -> bool:
        # write code here
        stk = []
        star_stk = []
        for index, ch in enumerate(s):
            if ch == "(":
                stk.append((index, ch))

            elif ch == ")":
                if stk and stk[-1][1] == "(":
                    stk.pop()
                elif len(star_stk) > 0:
                    star_stk.pop()
                else:
                    return False
            elif ch == "*":
                star_stk.append((index, ch))

        print(f"stk:{stk}\nstar_stk:{star_stk}")
		
		# 这里需要判断 "*"出现在"("后才合法.
        while len(stk) > 0 and len(star_stk) > 0:
            left = stk.pop()
            star = star_stk.pop()
            if star[0] < left[0]:
                return False

        if len(stk) == 0:
            return True

        return False