LeetCode 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。

样例

输入：s = "))()))", locked = "010100"
输出：true
解释：locked[1] == '1' 和 locked[3] == '1'，所以我们无法改变 s[1] 或者 s[3]。
我们可以将 s[0] 和 s[4] 变为 '('，不改变 s[2] 和 s[5]，使 s 变为有效字符串。


输入：s = "()()", locked = "0000"
输出：true
解释：我们不需要做任何改变，因为 s 已经是有效字符串了。


输入：s = ")", locked = "0"
输出：false
解释：locked 允许改变 s[0] 。
但无论将 s[0] 变为 '(' 或者 ')' 都无法使 s 变为有效字符串。

限制

• n == s.length == locked.length
• 1 <= n <= 10^5
• s[i] 要么是 '(' 要么是 ')'。
• locked[i] 要么是 '0' 要么是 '1'。

---

算法

(贪心思维) \(O(n)\)

判断一个合法的括号序列有两个条件：

1. 左括号数量等于右括号数量
2. 任何一个前缀中左括号数量小于等于右括号数量

具体实现：可以初始话变量x，如果遇到左括号，x++；如果遇到右括号x--；如果中途x<0，则为非法括号序列，如果最终x=0，则说明为合法的括号序列。

该题，首先先将所有可以改变的位置都变为右括号，定义x记录当前多余的左括号的情况，cnt记录可变的位置数目。如果当前 x<0，则可以修改之前可变位置的某一个右括号为左括号，使得 x+=2，cnt-=1。如果没有可修改的位置，则表示无法变为有效字符串。最终，如果 x=0，则说明可以变为有效字符串。

时间复杂度

• 遍历数组一次，故总时间复杂度为 \(O(n)\)。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool canBeValid(string s, string locked) {
        const int n = s.size();

        int x = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            if (locked[i] == '0') {
                s[i] = ')';
                cnt++;
            }

            if (s[i] == '(') x++;
            else x--;

            if (x < 0) {
                if (cnt == 0)
                    return false;

                cnt--;
                x += 2;
            }
        }

        return x == 0;
    }
};