题目：判断一个括号字符串是否有效
一个括号字符串是只由'('和')'组成的非空字符串。如果一个字符串满足下面任意一个条件，那么它就是有效的：
•字符串为().
•它可以表示为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 <= 105
•s[i]要么是'('要么是')'。
•locked[i]要么是'0'要么是'1'。
语言:C++
class Solution {
public:字符串长度判断
bool canBeValid(string s, string locked) {
int n = s.size();
int mx = 0;  // 可以达到的最大分数
int mn = 0;  // 可以达到的最小分数与最小有效前缀对应分数的较大值for (int i = 0; i < n; ++i) {
if (locked[i] == '1') {
// 此时对应字符无法更改
int diff;
if (s[i] == '(') {
diff = 1;
}
else {
diff = -1;
}
mx += diff;
mn = max(mn + diff, (i + 1) % 2);
}
else {
// 此时对应字符可以更改
++mx;
mn = max(mn - 1, (i + 1) % 2);
}
if (mx < mn) {
// 此时该前缀无法变为有效前缀
return false;
}
}
// 最终确定 s 能否通过变换使得分数为 0（成为有效字符串）
return mn == 0;
}
};
语言:C++
class Solution {
public:
bool canBeValid(string s, string locked) {
int n = s.size();
// 奇数长度一定无法配对
if (n & 1) return false;
// 左侧剩余unlock数量
int leftUnlock = 0;
// 左侧未配对被lock '(' 的数量
int left = 0;
int i = 0, j = 0;
while (i < n) {
while (j < n && locked[j] != '1') j++;
if (j == n) break;
leftUnlock += j - i;
if (s[j] == ')') {
if (left == 0) {
// 没有配对的lock 消耗unlock
if (leftUnlock == 0) return false;
leftUnlock--;
} else {
left--;
}
} else {
left++;
}
i = j + 1;
j = i;
}
int rightUnlock = 0;
int right = 0;
i = n - 1, j = n - 1;
while (i >= 0) {
while (j >= 0 && locked[j] != '1') j--;
if (j < 0) break;
rightUnlock += i - j;
if (s[j] == '(') {
if (right == 0) {
if (rightUnlock == 0) return false;
rightUnlock--;
} else {
right--;
}
} else {
right++;
}
i = j - 1;
j = i;
}
return true;
}
};
语言:Python
class Solution:
def canBeValid(self, s: str, locked: str) -> bool:        n = len(s)
mx =0# 可以达到的最大分数
mn =0# 可以达到的最小分数与最小有效前缀对应分数的较大值
for i in range(n):
if locked[i] =='1':
# 此时对应字符无法更改
if s[i] =='(':
diff =1
else:
diff =-1
mx += diff
mn = max(mn + diff, (i +1) %2)
else:
# 此时对应字符可以更改
mx +=1
mn = max(mn -1, (i +1) %2)
if mx < mn:
# 此时该前缀无法变为有效前缀
return False
# 最终确定 s 能否通过变换使得分数为 0（成为有效字符串）
return mn ==0
语言:go
func canBeValid(s string, locked string) bool {
if len(s)%2 == 1 {
return false
}
// 注：由于这里 len(s) 是偶数，所以循环结束后 x 也是偶数（这意味着可以通过配对来让括号平衡度为 0），无需判断 x 是否为奇数
// x 是偶数是因为每遍历一个字符必然会改变 x 的奇偶性，而 x 的奇偶性在发生偶数次变化后的结果是 x 的奇偶性不变
x := 0
for i, ch := range s {
if ch == '(' || locked[i] == '0' {
x++
} else if x > 0 {
x--
} else {
return false
}
}
x = 0
for i := len(s) - 1; i >= 0; i-- {
if s[i] == ')' || locked[i] == '0' {
x++
} else if x > 0 {
x--
} else {
return false
}
}
return true
}
语言:Java
class Solution {
public boolean canBeValid(String s, String locked) {
int n = s.length();
if((n&1) == 1) return false;
/
/left 是最小平衡值 right是最大平衡值
int left = 0 , right = 0;
for(int i = 0;i < n;i++){
left += left == 0 || s.charAt(i) == '(' && locked.charAt(i) =='1' ? 1 : -1;            right += locked.charAt(i) == '1' && s.charAt(i) == ')' ? -1 : 1;
if(left > right) return false;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。