leetcode [678] 有效的括号字符串

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。

示例 1:

输入: "()"
输出: True

示例 2:

输入: "(*)"
输出: True

示例 3:

输入: "(*))"
输出: True

注意:

字符串大小将在 [1，100] 范围内。

第一种解法是栈题解:

使用两个栈，left存左括号，star存“*”，存储的内容是字符在字符串中的下标。

1. 遍历字符串的每一个字符，如果是“（”存储下标到left中；
2. 如果是“*”存储下标到star中；
3. 如果是“）”，先从left中获取“（”，并将栈顶元素出栈，如果left为空，则从star中获取“*”，将栈顶元素出栈，如果star也为空，则返回false；
4. 按照1 2 3 遍历完字符串之后，遍历left，与“*”匹配；
5. 如果left为空，返回true；
6. 如果left不为空，遍历left，从star栈顶出栈一个“”，如果“”的下标小于left的“（”的下标，那么返回false；如果大于，则left栈顶出栈，star栈顶出栈，进行下一轮比较；
7. 如果最后left还有值，star为空，返回false；如果left为空，star有值，返回true。

class Solution:
    def checkValidString(self, s: str) -> bool:
        left_stack = []
        star_stack = []
        for i, ss in enumerate(s):
            if ss == '(':
                left_stack.append(i)
            elif ss == '*':
                star_stack.append(i)
            elif ss == ')':
                if left_stack:
                    left_stack.pop()
                elif star_stack:
                    star_stack.pop()
                else:
                    return False

        if not left_stack: return True
        while left_stack:
            if star_stack and star_stack[-1] > left_stack[-1]:
                star_stack.pop()
                left_stack.pop()
            else:
                return False
        return True

第二种解法来自题解:

用一个变量delta维护当前左括号的数量，左括号+1、右括号-1：

如果任意时刻有delta < 0说明右括号比左括号多，直接失败 如果最终有delta == 0说明平衡，才成功。

这里由于*可以变成3种字符，如果用贪心法也是可以的：维护当前左括号的数量范围[L, R]，遇到(则同时加1、遇到)则同时减1、遇到*则扩展范围(–L, ++R)，同理：

如果任意时刻有R < 0，则失败

如果最后有L <= 0 <= R，才成功

因为加1、减1的过程会保证[L, R]是连续整数区间，所以我们只需要维护区间的左右边界，而不需要维护该区间中的所有数字。

class Solution:
    def checkValidString(self, s: str) -> bool:
        L, R = 0, 0 # 维护当前左括号的数量范围：[L, R]

        for ch in s:
            if ch == '(':
                L += 1
                R += 1
            elif ch == ')':
                if L > 0:  
                    L -= 1
                if R > 0: 
                    R -= 1
                else:
                    return False
            elif ch == '*':
                if L > 0: 
                    L -= 1
                R += 1

        return L <= 0 <= R # 最后要能取到0