【LeetCode】括号问题——2116. 判断一个括号字符串是否有效（解法一）
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 。
示例 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 变为有效字符串。
示例 4：
输入：s = "(((())(((())", locked = "111111010111" 输出：true 解释：locked 允许我们改变 s[6] 和 s[8]。 我们将 s[6] 和 s[8] 改为 ')' 使 s 变为有效字符串。
提示：
n == s.length == locked.length- 1 <= n <= 10^5
s[i]要么是'('要么是')'。locked[i]要么是'0'要么是'1'。
解题思路
题目解析
在字符串匹配中有一个核心思路：
- 对于一个有效字符串
"()"而言，其左右括号的数量一定相等
从这个思路出发，当我们来判断一个字符串是否为有效字符串，我们只需要判断其左右字符的个数是否相等。即当一个字符串为")))((("，那我们可以判定它为有效字符串。
在这个基础上，由于不同题目的限制，我们需要知道在本题中怎样才是匹配成功，怎么样是匹配失败：
- 左括号
'('只能与其右侧的右括号')'完成匹配 - 右括号
')'只能与其左侧的左括号'('完成匹配
在这个规则上如果我们再来看该字符串")))((("，此时我们会发现，虽然左括号与右括号的数量一致，但是他们都没有能够正常与之匹配的括号，因此该字符串为无效字符串。
在本题中，还给出了一个条件，对于每个字符，都会通过'0'与'1'来记录其是否可以改变，那也就是说，还是这个字符串")))((("，当它对应的locked值为"000000"时，我们则可以将其变为"((()))"，此时该字符串又变为了有效字符串。
接下来我们就需要判断一个给定的字符串是否为有效字符串，有两种解题思路——栈、数学。在今天的内容中，我们会介绍第一种解题思路——栈。
方法一：栈
在这个问题中出现了两种类型的字符——可变括号与不可变括号：
- 可变括号只要数量为偶数，即可全部匹配
- 不可变括号只能进行
'('与')'匹配
因此我们不妨通过维护两个栈stack1与stack2来完成两类括号的匹配工作：
stack1用于维护不可变字符，记录所有不可变字符对应下标stack2用于维护可变字符，记录所有可变字符对应下标
我们通过从左往右遍历字符串s的方式完成括号的匹配工作，括号的匹配规则如下：
- 不可变左括号
'('只能与其右侧的右括号')'完成匹配 - 不可变右括号
')'只能与其左侧的左括号'('完成匹配 - 可变括号可以与其左侧的左括号
'('完成匹配 - 可变括号可以与其右侧的右括号
')'完成匹配
为了确保所有括号都能够正常匹配，因此我们通过先完成不可变括号的匹配工作，再处理可变括号和剩余不可变括号的匹配工作。
处理步骤：
- 遇到可变括号时，在
stack2中记录该括号的下标，即该元素下标入栈； - 遇到不可变括号时：
- 当括号为
'('，该元素下标入栈 - 当括号为')'：
- 若栈非空，则栈顶元素出栈
- 若栈为空，则该元素下标入栈
- 当括号为
- 完成字符串中所有元素的记录
当元素全部记录完，此时stack1中都是由不可变且未完成匹配的元素，stack2中全部为可变元素；
接下来我们继续完成剩余不可变元素的匹配工作：
- 通过
n来记录可变字符无法与不可变字符完成匹配的数量 - 使用
key1与key2来记录stack1与stack2栈顶元素的下标 - 判断
s[key1]的括号方向以及key1与key2的大小：- 当
s[key1] == ')'且key1 > key2时，能匹配成功，此时双栈栈顶元素出栈 - 当
s[key1] == '('且key1 < key2时，能匹配成功，此时双栈栈顶元素出栈 - 否则匹配失败，记录失败的可变字符个数，
stack2栈顶元素出栈
- 当
这一阶段的匹配完成后，我们通过stack1与stack2的情况来判断是否全部匹配：
- 如果
stack1为空栈，则说明不可变字符全部完成匹配，否则匹配失败 - 如果
stack2中剩余字符数量和n记录的数量之和为偶数，则可变字符全部完成匹配，否则匹配失败
当可变字符与不可变字符同时完成匹配，该字符串才为有效字符串，否则无效；
编写代码
方法一：栈
C语言
代码语言：javascript代码运行次数：0运行复制//判断是否需要入栈
bool Need_Push(char* s, int* stack, int i, int top) {
// 栈为空
bool flag1 = top == 0;
bool flag2 = false;
bool flag3 = false;
// 匹配失败
if (!flag1) {
// 新元素与栈顶元素相等
flag2 = s[stack[top - 1]] == s[i];
// 栈顶为左括号，新元素为右括号
flag3 = s[stack[top - 1]] == ')' && s[i] == '(';
}
return flag1 || flag2 || flag3;
}
bool canBeValid(char* s, char* locked) {
int len = strlen(s);
int* stack1 = (int*)calloc(len, sizeof(int));
assert(stack1);
int top1 = 0;
int* stack2 = (int*)calloc(len, sizeof(int));
assert(stack2);
int top2 = 0;
for (int i = 0; i < len; i++) {
// 不可变
if (locked[i] == '1') {
if (Need_Push(s, stack1, i, top1)) {
stack1[top1] = i;
top1 += 1;
}
else {
top1 -= 1;
}
}
// 可变
else {
stack2[top2] = i;
top2 += 1;
}
}
int n = 0;
while (top1 && top2) {
int key1 = stack1[top1 - 1], key2 = stack2[top2 - 1];
// 不可变栈，栈顶为左括号，可变栈栈顶元素位于不可变栈左侧
bool flag1 = s[key1] == ')' && key2 < key1;
// 不可变栈，栈顶为右括号，可变栈栈顶元素位于右侧
bool flag2 = s[key1] == '(' && key2 > key1;
// 匹配成功
if (flag1 || flag2) {
top1 -= 1;
}
else {
// 记录可变栈中元素未与不可变栈中元素匹配成功的个数
n += 1;
}
top2 -= 1;
}
free(stack1);
free(stack2);
n += top2;
return top1 == 0 && n % 2 == 0;
}Python
代码语言：javascript代码运行次数：0运行复制class Solution(object):
def canBeValid1(self, s, locked):
"""
:type s: str
:type locked: str
:rtype: bool
"""
len1 = len(s)
stack1 = [] # 不可变字符栈
top1 = 0
stack2 = [] # 可变字符栈
top2 = 0
for i in range(len1):
if locked[i] == '1':
# 非空栈，并且匹配成功，执行出栈操作
if top1 and s[i] == ')' and s[stack1[top1-1]] == '(':
stack1.pop()
top1 -= 1
# 空栈，或者匹配失败，入栈
else:
stack1.append(i)
top1 += 1
else:
stack2.append(i)
top2 += 1
n = 0
while top1 and top2:
key1 = stack1[top1 - 1]
key2 = stack2[top2 - 1]
# 匹配成功，出栈
if (s[key1] == ')' and key2 < key1) or (s[key1] == '(' and key2 > key1):
stack1.pop()
top1 -= 1
# 匹配失败，记录字符数量
else:
n += 1
stack2.pop()
top2 -= 1
n += top2
return top1 == 0 and n % 2 == 0代码测试
下面我们将写好的代码复制到力扣中进行测试，首先我们来测试一下C语言版：
可以看到，我们正常的通过了所有的测试用例。下面我们继续测试Python：
可以看到，我们同样通过了Python的所有测试用例。
算法分析
下面我们就来分析一下方法一的时间复杂度与空间复杂度，这里我们以C语言代码为例；
时间复杂度
在整个算法中，总共有两个循环，在第一个for循环中，存在一次函数调用。
首先我们来看一下调用的函数里面的时间复杂度：
代码语言：javascript代码运行次数：0运行复制//判断是否需要入栈
bool Need_Push(char* s, int* stack, int i, int top) {
// 栈为空
bool flag1 = top == 0; //O(1)
bool flag2 = false; //O(1)
bool flag3 = false; //O(1)
// 匹配失败
if (!flag1) { //O(1)
// 新元素与栈顶元素相等
flag2 = s[stack[top - 1]] == s[i]; //O(1)
// 栈顶为左括号，新元素为右括号
flag3 = s[stack[top - 1]] == ')' && s[i] == '('; //O(1)
}
return flag1 || flag2 || flag3; //O(1)
}在该函数中并不存在任何循环，因此函数的时间复杂度为O(1)。接下来我们就来看剩下的两个循环：
代码语言：javascript代码运行次数：0运行复制 for (int i = 0; i < len; i++) { //O(N)
// 不可变
if (locked[i] == '1') { //O(1)
if (Need_Push(s, stack1, i, top1)) { //O(1)
stack1[top1] = i; //O(1)
top1 += 1; //O(1)
}
else { //O(1)
top1 -= 1; //O(1)
}
}
// 可变
else { //O(1)
stack2[top2] = i; //O(1)
top2 += 1; //O(1)
}
}
int n = 0; //O(1)
while (top1 && top2) { //O(M)
int key1 = stack1[top1 - 1], key2 = stack2[top2 - 1];//O(1)
// 不可变栈，栈顶为左括号，可变栈栈顶元素位于不可变栈左侧
bool flag1 = s[key1] == ')' && key2 < key1; //O(1)
// 不可变栈，栈顶为右括号，可变栈栈顶元素位于右侧
bool flag2 = s[key1] == '(' && key2 > key1; //O(1)
// 匹配成功
if (flag1 || flag2) { //O(1)
top1 -= 1; //O(1)
}
else { //O(1)
// 记录可变栈中元素未与不可变栈中元素匹配成功的个数
n += 1; //O(1)
}
top2 -= 1; //O(1)
}在这两个循环中，第一个循环的时间复杂度为O(N)，第二个循环的时间复杂度为O(M)，其中 M <= N，因此总的时间复杂度为O(N)。
空间复杂度
在该算法中，涉及额外空间的就是栈空间的申请：
代码语言：javascript代码运行次数：0运行复制 int* stack1 = (int*)calloc(len, sizeof(int)); //O(N)
assert(stack1);
int top1 = 0;
int* stack2 = (int*)calloc(len, sizeof(int)); //O(N)
assert(stack2);
int top2 = 0;在算法中，我们申请了两个长度为len的栈空间，空间的数量随着len的变化而改变，因此其对应的空间复杂都均为O(N)，因此总的空间复杂度为:
小结
该算法的时间复杂度和空间复杂度分别为：
- 时间复杂度：O(N)
- 空间复杂度：O(N)
在下一篇内容中，我们将会介绍更优的算法，大家记得关注哦！！！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-23，如有侵权请联系 cloudcommunity@tencent 删除测试工作算法字符串leetcode
发布评论