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

题目链接

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

分析

记左括号为 $1$ 分，右括号为 $-1$ 分，括号字符串有效的条件等价于：该字符串的分数为 $0$，且该字符串任意前缀的分数均大于等于 $0$

由于字符串中存在可以更改的字符，我们创建两个变量 $min_cnt$ 和 $max_cnt$，分别记录当前前缀可以达到的最大和最小分数（即分别考虑将其变为左括号和右括号的情况）

当遍历计算途中未出现 $max_cnt < min_cnt$ 的情况，并且最后 $min_cnt = 0$ ，字符串有效

代码实现

class Solution {
public:
    bool canBeValid(string s, string locked) {
        if(s.size() % 2)
            return false;
      
        int max_cnt = 0, min_cnt = 0;

        for(int i = 0; i < s.size(); ++i) {
            if(locked[i] == '1') {
                int t = s[i] == '(' ? 1 : -1;
                max_cnt += t;
                min_cnt += t;
            }
            else {
                max_cnt++;
                min_cnt--;
            }
            min_cnt = min_cnt < 0 ? 1 : min_cnt;

            if(max_cnt < min_cnt)
                return false;
        }
      
        return min_cnt == 0;
    }
};

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$