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

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

题目描述

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

  • 字符串为 ()
  • 它可以表示为 ABAB 连接),其中 AB 都是有效括号字符串。
  • 它可以表示为 (A),其中 A 是一个有效括号字符串。

给你一个括号字符串 s 和一个字符串 locked,两者长度都为nlocked 是一个二进制字符串,只包含 '0''1'。对于 locked每一个 下标 i

  • 如果 locked[i]'1',你 不能 改变 s[i]
  • 如果 locked[i]'0',你 可以s[i] 变为 '(' 或者 ')'

如果你可以将 s 变为有效括号字符串,请你返回 true,否则返回 false

样例

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

输入: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;
    }
};
上一篇:python引用包错误记录(pycharm:ide报错, terminal:命令行运行不报错)


下一篇:Ext信息提示对话框