跳至主要內容

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


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

🟠 Medium  🔖  贪心 字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

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 with B), where A and B are valid parentheses strings.
  • It can be written as (A), where A 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 change s[i].
  • But if locked[i] is '0', you can change s[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'.

题目大意

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

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

给你一个括号字符串 s 和一个字符串 locked ,两者长度都为 nlocked 是一个二进制字符串,只包含 '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'

解题思路

  1. 长度约束

    • 如果字符串长度 s.length 是奇数,则直接返回 false,因为有效括号字符串长度必为偶数。
  2. 贪心验证

    • 从左向右遍历:
      • 用一个计数器 openCount 表示“可用的左括号数量”,包括未锁定的字符。
      • 如果遇到 '(' 或未锁定的字符 locked[i] == '0',则 openCount++
      • 如果遇到 ')' 并且 locked[i] == '1',则 openCount--
      • 如果 openCount 小于 0,说明右括号多于可用的左括号,直接返回 false
    • 从右向左遍历:
      • 用一个计数器 closeCount 表示“可用的右括号数量”。
      • 同理,更新 closeCount,并检查是否满足条件。

复杂度分析

  • 时间复杂度O(n),两次遍历字符串。
  • 空间复杂度O(1),使用了常数空间来存储计数器 openCountcloseCount

代码

/**
 * @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有效的括号[✓] 字符串🟢🀄️open in new window 🔗open in new window
22括号生成[✓]字符串 动态规划 回溯🟠🀄️open in new window 🔗open in new window
678有效的括号字符串[✓] 贪心 字符串 1+🟠🀄️open in new window 🔗open in new window
1249移除无效的括号 字符串🟠🀄️open in new window 🔗open in new window
2267检查是否有合法括号字符串路径数组 动态规划 矩阵🔴🀄️open in new window 🔗open in new window