括号匹配专题

678. 有效的括号字符串

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

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

字符串大小在 100 以内

方法一栈

因为 * 即可充当左括号，又可以充当右括号，我们为它独立设一个栈 star，然后再为 left 设立一个栈。

遍历过程中，遇到 * 则把坐标 push 到 star 中，遇到 ( 则把坐标 push 到 left 中，遇到 ) 时：

首先检查 left 是否有值，如果有则 pop。表示使用一个 ( 匹配当前的 )
如果 left 没有，则考虑 star，使用 * 来充当一个 (
否则，直接返回 false

结束后，如果 left 仍然有值，我们要考虑将剩余的 * 转为 ) 来匹配。每次检查 star 和 left 的栈顶元素 \(starIdx\) 和 \(leftIdx\)，如果有 \(starIdx > leftIdx\) 则表示可以匹配，否则直接返回 false。

最后 left 必须为空，而 star 可以不为空。

该方法的时间复杂度为 \(O(n)\)，空间复杂度为 \(O(n)\)。

C++

class Solution {
public:
    bool checkValidString(string s) {
        stack<int> left, star;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '*') {
                star.push(i);
            } else if (s[i] == '(') {
                left.push(i);
            } else {
                if (!left.empty()) {
                    left.pop();
                } else if (!star.empty()) {
                    star.pop();
                } else {
                    return false;
                }
            }
        }
        while (!left.empty() && !star.empty()) {
            int leftIdx = left.top(); left.pop();
            int starIdx = star.top(); star.pop();
            if (leftIdx > starIdx) {
                return false;
            }
        }
        return left.empty();
    }
};

方法二一次遍历

记括号序列中左括号的个数减去右括号的个数为 \(num\)，在合法括号序列中，任意一个前缀都满足 \(num \ge 0\)，并且整个串的 \(num = 0\)。

因此，在遍历带有 * 的括号串时，时刻维护前缀中 \(num\) 可能的最小值 \(mn\) 和最大值 \(mx\)。

对于 (，\(mn,mx\) 都 +1
对于 )，\(mn,mx\) 都 -1
对于 *，\(mn\) -1，\(mx\) +1

对于任意时刻，如果出现 \(mx \lt 0\) 的情况，则直接返回 false。如果出现 \(mn \lt 0\)，则令 \(mn = 0\) 将其重新归位。

最终判定 \(mn = 0\) 是否成立即可。

该方法的时间复杂度为 \(O(n)\)，空间复杂度为 \(O(1)\)。

C++

class Solution {
public:
    bool checkValidString(string s) {
        int mn = 0, mx = 0;
        for (auto ch : s) {
            if (ch == '(') {
                mn++;
                mx++;
            } else if (ch == ')') {
                mn--;
                mx--;
            } else {
                mn--;
                mx++;
            }
            if (mx < 0) {
                return false;
            }
            mn = max(mn, 0);
        }
        return mn == 0;
    }
};

2116. 判断一个括号字符串是否有效

一个括号字符串是只由 '(' 和 ')' 组成的非空字符串。如果一个字符串满足下面任意一个条件，那么它就是有效的：

字符串为 ().
它可以表示为 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串。
它可以表示为 (A) ，其中 A 是一个有效括号字符串。

给你一个括号字符串 s 和一个字符串 \(locked\) ，两者长度都为 \(n\) 。\(locked\) 是一个二进制字符串，只包含 '0' 和 '1' 。对于 \(locked\) 中每一个下标 i ：

如果 \(locked[i]\) 是 '1' ，你不能改变 \(s[i]\) 。
如果 \(locked[i]\) 是 '0' ，你可以将 \(s[i]\) 变为 '(' 或者 ')' 。如果你可以将 s 变为有效括号字符串，请你返回 true ，否则返回 false 。

数据范围：\(n \le 10^5\)

这个题和 678 题目很类似，在 678 中，* 不仅可以变为 ( 和 )，还可以变为空格。但是在本题中，只可以变为 ( 和 )。

因此，在本题中，左括号和右括号的个数是一定的，我们可以预先算出来。

首先，当 \(n\) 为奇数时，直接返回 \(false\)。

然后假设 \(\textit{left}\) 和 \(\textit{right}\) 分别为括号串中不可变的 ( 和 ) 的个数，令 \(need = n / 2\)，如果 \(max(left, right) > need\) 则直接返回 false。

接下来，我们总是优先把前 \(need - left\) 个可置换的位置换为 (，因为贪心策略告诉我们，前缀中左括号数越多成功匹配的可能性越大。具体的判断方法请参考代码。

该方法时间复杂度 \(O(n)\)，空间复杂度为 \(O(1)\)。

C++

class Solution {
public:
    bool canBeValid(string s, string locked) {
        int n = s.size();
        if (n & 1) return false;
        int l = 0, r = 0, x = 0;
        for (int i = 0; i < n; i++) {
            if (locked[i] == '1') {
                if (s[i] == '(') l++;
                else r++;
            } else {
                x++;
            }
        }
        int need = n / 2;
        if (l > need || r > need) return false;
        int pre = need - l, cur = 0;
        for (int i = 0; i < n; i++) {
            if (locked[i] == '1') {
                if (s[i] == '(') cur++;
                else cur--;
            } else {
                if (pre > 0) cur++, pre--;
                else cur--;
            }
            if (cur < 0) return false;
        }
        return cur == 0;
    }
};

本文访问次

括号匹配专题

678. 有效的括号字符串

方法一 栈

方法二 一次遍历

2116. 判断一个括号字符串是否有效

方法一栈

方法二一次遍历