【C++ 数学括号匹配】2116. 判断一个括号字符串是否有效|2037

本文涉及知识点

数学括号匹配

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

一个括号字符串是只由 ‘(’ 和 ‘)’ 组成的非空字符串。如果一个字符串满足下面任意一个条件，那么它就是有效的：
字符串为 ().
它可以表示为 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 。
示例 1：
在这里插入图片描述

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

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

输入：s = “)”, locked = “0”
输出：false
解释：locked 允许改变 s[0] 。
但无论将 s[0] 变为 ‘(’ 或者 ‘)’ 都无法使 s 变为有效字符串。
提示：
n == s.length == locked.length
1 <= n <= 10⁵
s[i] 要么是 ‘(’ 要么是 ‘)’ 。
locked[i] 要么是 ‘0’ 要么是 ‘1’ 。

数学括号匹配

左括号的分数是1，右括号是-1。
v[i] =s[0…i]分值之和。
括号合法的两个条件：
一， $\forall$ i ,v[i] >=0。
二，v.back() 是0。
三轮循环：
一，从左到右计算v[i]，如果v[i] <0。必须：将s[0…i]中的一个右括号改成左括号。改任意一个对条件一和条件二是一样的。我们就改最左的。用队列记录可以修改右括号。
二，计算结束后，如果v.back()>0。则需要将v.back() /2个左括号改成右括号，修改下标大的不劣于下标小的。因为前者对条件一的影响小。用栈可以修改的左括号。
三，判断修改后的s是否合法。
空间复杂度：O(n)
时间复杂度：O(n)

代码

核心代码

class Solution {public:bool canBeValid(string s, string locked) {queue<int> que;stack<int> sta;int sum = 0;for (int i = 0; i < s.length(); i++) {if ('0' == locked[i]) {if (')' == s[i]) { que.emplace(i); }else { sta.emplace(i); }}sum += ('(' == s[i] ? 1 : -1);if (sum < 0) {if (que.empty()) { return false; }s[que.front()] = '(';que.pop();sum += 2;}}sum /= 2;if (sta.size() < sum) { return false; }for (; sum > 0; sum--) {s[sta.top()] = ')';sta.pop();}for (int i = 0; i < s.length(); i++) {					sum += ('(' == s[i] ? 1 : -1);if (sum < 0) {return false;}}return 0 == sum;}};

单元测试

	string s,  locked;TEST_METHOD(TestMethod11){s = "))()))", locked = "010100";auto res = Solution().canBeValid(s, locked);AssertEx(true, res);}TEST_METHOD(TestMethod12){s = "))()))", locked = "010100";auto res = Solution().canBeValid(s, locked);AssertEx(true, res);}TEST_METHOD(TestMethod13){s = ")", locked = "0";auto res = Solution().canBeValid(s, locked);AssertEx(false, res);}TEST_METHOD(TestMethod14){s = "())(()(()(())()())(())((())(()())((())))))(((((((())(()))))(", locked = "100011110110011011010111100111011101111110000101001101001111";auto res = Solution().canBeValid(s, locked);AssertEx(false, res);}