678. 有效的括号字符串

Difficulty
Medium
Tags
栈
URL
https://leetcode.cn/problems/valid-parenthesis-string/
Star
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
  1. 任何左括号 ( 必须有相应的右括号 )。
  1. 任何右括号 ) 必须有相应的左括号 ( 。
  1. 左括号 ( 必须在对应的右括号之前 )。
  1. 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
  1. 一个空字符串也被视为有效字符串。
示例 1:
输入: "()"
输出: True
示例 2:
输入: "(*)"
输出: True
示例 3:
输入: "(*))"
输出: True
注意:
  1. 字符串大小将在 [1，100] 范围内。

法 1 双栈

思路
我们很自然的会仍然用两个栈记录目前为止不能匹配的字符，也就是*和(，每次出现右括号我们就应该去两个栈匹配可以匹配的左括号。
而*可以作为任何括号，也可以作为空字符串，所以我们应该优先用左括号匹配，所以我们出栈的策略如下：
  • 遇到左括号，直接进栈，记录括号的位置。
  • 遇到星号，直接进栈，记录星号的位置。
  • 遇到右括号：
    • 左括号栈里有元素，直接出栈。
    • 左括号栈里无元素，*栈里有元素，直接出栈。无元素的话就已经匹配失败了。
如果遍历完数组的话，我们可能会发现左括号栈里还有结余元素。如果是20题的情况，已经失败了。但现在我们可能还有一些星号可以作为右括号用，所以我们进行下面的匹配操作： 对左括号栈逐一出栈，然后去看此时星号栈的栈顶，如果栈顶元素的位置大于左括号栈顶元素的位置，说明星号在括号的右侧，可以匹配。否则不可。
题解
class Solution:
    def checkValidString(self, s: str) -> bool:
        stack_a = []
        stack_b = []

        for i in range(0, len(s)):
            if s[i] == "(":
                stack_a.append(i)
            elif s[i] == "*":
                stack_b.append(i)
            # 遇到右括号，优先匹配左括号，再去匹配*
            else:
                if len(stack_a) > 0:
                    stack_a.pop()
                else:
                    if len(stack_b) == 0:
                        return False
                    stack_b.pop()

        # 匹配多余的左括号
        while len(stack_a):
            if len(stack_b) == 0:
                return False
            if stack_b[-1] > stack_a[-1]:
                stack_b.pop()
                stack_a.pop()
            else:
                return False

        return True

法2 虚拟栈 模拟

思路
令左括号的得分为 1；右括号的得分为 -1。那么对于合法的方案而言，必定满足最终得分为 0。
同时由于本题存在 *，因此我们需要记录得分的区间区间是多少，而不仅是一个具体的得分。
具体的，使用两个变量 l 和 r 分别表示「最低得分」和「最高得分」。
根据当前处理到的字符进行分情况讨论：
  • 当前字符为 ( : l 和 r 同时加一；
  • 当前字符为 ) : l 和 r 同时减一；
  • 当前字符为 * : 如果 * 代指成 ( 的话，l 和 r 都进行加一；如果 * 代指成 ) 的话，l 和 r 都进行减一；如果 * 不变的话，l 和 r 均不发生变化。
      • 因此总的 l 的变化为减一，总的 r 的变化为加一。
需要注意的是，在匹配过程中如果 l 为负数，需要重置为 0，因为如果当前序列本身为不合法括号序列的话，增加 ( 必然还是不合法。同时，当出现 l > r 说明上界为负数，即右括号过多，必然为非合法方案，返回 False。
也可以把 l, r理解为当前为匹配左括号的数目，因为*号的存在，(的数目此刻变成了一个区间[l, r]
题解
class Solution:
    def checkValidString(self, s: str) -> bool:
        l, r = 0, 0
        for i in range(0, len(s)):
            if s[i] == "(":
                l += 1
                r += 1
            elif s[i] == ")":
                l -= 1
                r -= 1
            else:
                l -= 1
                r += 1

            l = max(0, l)
            if l > r:
                return False

        return l == 0