2116. 判断一个括号字符串是否有效
2116. 判断一个括号字符串是否有效
🟠 Medium 🔖 栈
贪心
字符串
🔗 力扣
LeetCode
题目
A parentheses string is a non-empty string consisting only of '('
and ')'
. It is valid if any of the following conditions is true :
- It is
()
. - It can be written as
AB
(A
concatenated withB
), whereA
andB
are valid parentheses strings. - It can be written as
(A)
, whereA
is a valid parentheses string.
You are given a parentheses string s
and a string locked
, both of length n
. locked
is a binary string consisting only of '0'
s and '1'
s. For each index i
of locked
,
- If
locked[i]
is'1'
, you cannot changes[i]
. - But if
locked[i]
is'0'
, you can changes[i]
to either'('
or')'
.
Return true
if you can makes
a valid parentheses string. Otherwise, return false
.
Example 1:

Input: s = "))()))", locked = "010100"
Output: true
Explanation: locked[1] == '1' and locked[3] == '1', so we cannot change s[1] or s[3].
We change s[0] and s[4] to '(' while leaving s[2] and s[5] unchanged to make s valid.
Example 2:
Input: s = "()()", locked = "0000"
Output: true
Explanation: We do not need to make any changes because s is already valid.
Example 3:
Input: s = ")", locked = "0"
Output: false
Explanation: locked permits us to change s[0].
Changing s[0] to either '(' or ')' will not make s valid.
Constraints:
n == s.length == locked.length
1 <= n <= 10^5
s[i]
is either'('
or')'
.locked[i]
is either'0'
or'1'
.
题目大意
一个括号字符串是只由 '('
和 ')'
组成的 非空 字符串。如果一个字符串满足下面 任意 一个条件,那么它就是有效的:
- 字符串为
()
. - 它可以表示为
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^5
s[i]
要么是'('
要么是')'
。locked[i]
要么是'0'
要么是'1'
。
解题思路
长度约束
- 如果字符串长度
s.length
是奇数,则直接返回false
,因为有效括号字符串长度必为偶数。
- 如果字符串长度
贪心验证
- 从左向右遍历:
- 用一个计数器
openCount
表示“可用的左括号数量”,包括未锁定的字符。 - 如果遇到
'('
或未锁定的字符locked[i] == '0'
,则openCount++
。 - 如果遇到
')'
并且locked[i] == '1'
,则openCount--
。 - 如果
openCount
小于 0,说明右括号多于可用的左括号,直接返回false
。
- 用一个计数器
- 从右向左遍历:
- 用一个计数器
closeCount
表示“可用的右括号数量”。 - 同理,更新
closeCount
,并检查是否满足条件。
- 用一个计数器
- 从左向右遍历:
复杂度分析
- 时间复杂度:
O(n)
,两次遍历字符串。 - 空间复杂度:
O(1)
,使用了常数空间来存储计数器openCount
和closeCount
。
代码
/**
* @param {string} s
* @param {string} locked
* @return {boolean}
*/
var canBeValid = function (s, locked) {
if (s.length % 2 == 1) return false;
let openCount = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] == '(' || locked[i] == '0') {
openCount++;
} else {
openCount--;
}
if (openCount < 0) return false; // 右括号过多
}
let closeCount = 0;
for (let i = s.length - 1; i >= 0; i--) {
if (s[i] == ')' || locked[i] == '0') {
closeCount++;
} else {
closeCount--;
}
if (closeCount < 0) return false; // 左括号过多
}
return true;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
20 | 有效的括号 | [✓] | 栈 字符串 | 🟢 | 🀄️ 🔗 |
22 | 括号生成 | [✓] | 字符串 动态规划 回溯 | 🟠 | 🀄️ 🔗 |
678 | 有效的括号字符串 | [✓] | 栈 贪心 字符串 1+ | 🟠 | 🀄️ 🔗 |
1249 | 移除无效的括号 | 栈 字符串 | 🟠 | 🀄️ 🔗 | |
2267 | 检查是否有合法括号字符串路径 | 数组 动态规划 矩阵 | 🔴 | 🀄️ 🔗 |