难度: Medium
给你一个只包含三种字符的字符串，支持的字符类型分别是 '('、')' 和 '*'。请你检验这个字符串是否为有效字符串，如果是有效字符串返回 true 。
有效字符串符合如下规则：
'(' 必须有相应的右括号 ')'。')' 必须有相应的左括号 '(' 。'(' 必须在对应的右括号之前 ')'。'*' 可以被视为单个右括号 ')' ，或单个左括号 '(' ，或一个空字符串。示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "(*)" 输出：true
示例 3：
输入：s = "(*))" 输出：true
提示：
1 <= s.length <= 100s[i] 为 '('、')' 或 '*'运行时间: 22 ms
内存: 15.9 MB
class Solution:
def checkValidString(self, s: str) -> bool:
l, sign = [], []
for i in range(len(s)):
if s[i] == "(":
l.append(i)
elif s[i] == ")":
if l:
l.pop()
elif sign:
sign.pop()
else:
return False
else:
sign.append(i)
i, j = len(l)-1, len(sign)-1
while i >= 0 and j >= 0:
if l[i] < sign[j]:
i -= 1
j -= 1
else:
return False
return i < 0
这个题解使用两个栈 l 和 sign 分别存储左括号 '(' 和星号 '*' 的下标。遍历字符串，遇到左括号入栈 l，遇到星号入栈 sign，遇到右括号则优先弹出 l 栈顶元素，若 l 为空则弹出 sign 栈顶元素，若 sign 也为空说明没有左括号与当前右括号匹配，返回 false。最后从 l 和 sign 的栈顶开始比较下标，若 l 栈顶元素下标大于 sign 栈顶元素的下标，说明无法匹配，返回 false。若最终 l 栈为空则说明所有的左括号都被匹配，字符串有效，返回 true。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def checkValidString(self, s: str) -> bool:
l, sign = [], [] # l 栈存储左括号下标，sign 栈存储星号下标
for i in range(len(s)):
if s[i] == "(":
l.append(i) # 遇到左括号，下标入栈 l
elif s[i] == ")":
if l:
l.pop() # 遇到右括号，优先弹出 l 栈顶元素
elif sign:
sign.pop() # l 为空则弹出 sign 栈顶元素
else:
return False # l 和 sign 都为空，没有括号匹配，返回 false
else:
sign.append(i) # 遇到星号，下标入栈 sign
i, j = len(l)-1, len(sign)-1
while i >= 0 and j >= 0: # 从 l 和 sign 栈顶开始比较下标
if l[i] < sign[j]: # 若 l 栈顶元素下标小于 sign 栈顶元素的下标
i -= 1 # l 和 sign 栈顶元素都不再考虑
j -= 1
else:
return False # 若 l 栈顶元素下标大于 sign 栈顶元素下标，则无法匹配，返回 false
return i < 0 # 若最终 l 中所有左括号都被匹配，则字符串有效，返回 true
在处理右括号时，优先选择弹出存储左括号的栈`l`是因为左括号与右括号直接匹配是标准的括号匹配规则，这可以直接验证括号的合法性。如果选择用星号来匹配右括号，则实际上是将星号当作左括号使用，这种情况应当是备选方案，在没有左括号可用时才考虑。因此，优先使用左括号栈可以直接、准确地处理大部分标准情况，而星号作为一种灵活的替代品，用于处理特殊或不足的场景。
如果在遍历结束后，`sign`栈中的星号下标全都小于`l`栈中的左括号下标，那么这意味着所有的星号都无法作为右括号来匹配这些左括号。因为星号如果作为右括号使用，必须出现在对应左括号的右侧。在这种情况下，剩余的左括号无法找到合适的匹配项，算法将返回`false`，表明字符串不是有效的括号组合。这是算法设计的正确行为，确保了只有当所有的左括号都能被正确匹配时，才认为输入字符串是有效的。
如果在最后的栈下标比较过程中，`sign`栈为空但`l`栈还有剩余元素，意味着没有足够的星号可以作为右括号来匹配剩余的左括号。在这种情况下，剩余的左括号无法被匹配，因此算法将返回`false`，表示字符串不是一个有效的括号字符串。这反映了算法确保每一个左括号都必须找到一个对应的右括号或者一个作为右括号的星号才能构成有效的括号匹配。
算法在处理星号时将其下标存入`sign`栈，并不意味着所有的星号都被默认先当作右括号处理。星号在算法中具有多重可能性：它可以作为左括号、右括号或者什么都不做。存储星号的下标是为了在处理完所有字符后，根据需要动态决定每个星号的角色。在最终的栈下标比较过程中，根据星号和左括号的相对位置，动态决定每个星号是否作为右括号或忽略。这种处理方式灵活地考虑了星号的多重可能性，并确保所有的左括号都能找到合适的匹配项，从而验证字符串的有效性。