判断一个括号字符串是否有效
难度:
标签:
题目描述
一个括号字符串是只由 '(' 和 ')' 组成的 非空 字符串。如果一个字符串满足下面 任意 一个条件，那么它就是有效的：
- 字符串为
(). - 它可以表示为
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.length1 <= n <= 105s[i]要么是'('要么是')'。locked[i]要么是'0'要么是'1'。
代码结果
运行时间: 100 ms, 内存: 20.9 MB
/*
* 题目思路：
* 使用Java Stream API 实现相同的逻辑，遍历两次字符串 s，统计左括号和右括号的数量，
* 并通过 locked 来判断是否可以修改括号，最后检查是否能组成有效的括号字符串。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean canBeValid(String s, String locked) {
int n = s.length();
if (n % 2 != 0) return false;
int open = 0, close = 0;
boolean isValid = IntStream.range(0, n).allMatch(i -> {
if (locked.charAt(i) == '0' || s.charAt(i) == '(') {
open++;
} else {
close++;
}
return close <= open;
});
if (!isValid) return false;
open = 0;
close = 0;
return IntStream.range(0, n).map(i -> n - 1 - i).allMatch(i -> {
if (locked.charAt(i) == '0' || s.charAt(i) == ')') {
close++;
} else {
open++;
}
return open <= close;
});
}
}
解释
方法:
这个题解首先遍历一次输入字符串s，同时记录每个可以变换的字符位置（'0' in locked）到star列表，以及左括号的位置到left列表。如果当前位置锁定且为右括号，则尝试匹配一个未匹配的左括号或可变字符；如果两者都匹配不到，则直接返回false。第二次遍历在遍历结束后，处理剩余的left和star。如果left中的左括号索引在star中任何可变字符的索引之前，即无法用可变字符匹配成对的括号，那么返回false。如果star列表中还有剩余的可变字符，只要数量是偶数，就可以配对成功，否则返回false。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
题解中提到两次遍历，第一次遍历处理锁定和未锁定的括号，第二次处理剩余的括号。在第二次遍历中，如何确保所有可能的匹配都已经被尝试？
▷🦆
在处理剩余的`left`和`star`列表时，如果`left`中的索引在`star`中对应的索引之前，则返回false。这里的逻辑是基于什么考虑？为什么left索引必须在star索引之后才能匹配成功？
▷🦆
算法中有一个条件：如果`star`列表有剩余且数量是偶数，则可以将它们配对成功。能否详细解释为什么偶数的`star`元素可以保证配对成功？
▷