发表于 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

• LC 题目链接