JZX轻语：简
LeetCode 678 - 有效的括号字符串
发表于2024年04月10日
经典括号匹配题目的衍生题目，在此基础上新增了一个通配符(可以用作左括号、右括号或者空字符)。首先按通常的做法来做，并记录已读取的星号数(先不使用, 用一个栈来存储出现的位置)，如果当前处理右括号但左括号已经用完，则使用一个星号(弹出栈顶，如果栈为空则直接返回false)。当处理完所有的字符串后，还有多余的左括号需要处理，则比对左括号的位置和星号的位置(如有，如果没有星号则返回false)，如果星号的位置右于左括号的位置，则弹出并继续，否则，返回false。如果所有的左括号处理完毕，则返回true。
还有个小细节需要证明下: 字符串处理完毕后，如果有多余的左括号，则其右边的星号(如有)不会被提前消耗，这是因为星号被消耗的前提是没有左括号，如果其被消耗而左边还有左括号，这与假设矛盾。
class Solution:
def checkValidString(self, s: str) -> bool:
left_brace_stack = []
star_stack = []
for i, ch in enumerate(s):
if ch == '(':
left_brace_stack.append(i)
elif ch == ')':
if not left_brace_stack:
if not star_stack:
return False
star_stack.pop()
else:
left_brace_stack.pop()
else:
star_stack.append(i)
# 可能会有多余的左括号, 需要将*号转为右括号
while left_brace_stack:
left_brace_index = left_brace_stack.pop()
if not star_stack or left_brace_index > star_stack[-1]:
return False
star_stack.pop()
return True