题目
一个括号字符串是只由 '(' 和 ')' 组成的 非空 字符串。如果一个字符串满足下面 任意 一个条件，那么它就是有效的：
-
字符串为
(). -
它可以表示为
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 <= 105 -
s[i]要么是'('要么是')'。 -
locked[i]要么是'0'要么是'1'。
思路
一看到题目是判断合法括号，就想到了这题好像我会啊，不就是用栈来判断，左括号压栈，右括号出栈，如果栈最后为空，且中间也没有不够用（遇到右括号，但是栈为空导致无元素可以弹出），那么就是合法括号。
如果只有一种括号，这里还可以优化，不需要真正去压栈和出栈，用一个变量，左括号就+1，右括号就-1，直到最后结果为0，且中间不存在任何时候是小于0的情况，就是合法括号。
本题略微有一些变化，求的是是否可以通过改变原始字符串，变成合法括号。一个合法的括号，必然满足如下条件：
-
长度为偶数，其中一半是左括号，一半是右括号
-
任意一个前缀，都满足左括号数量大于等于右括号数量
-
任意一个后缀，都满足右括号数量大于等于左括号数量
只有locked为1的位置，原始括号才不可变，其他位置的原始括号是可变的，即不用管原始括号是什么。具体操作上，我们可以做如下3步校验：
-
长度为偶数，如果为奇数，肯定不是合法的
-
对于任意一个前缀，贪心的认为，任何非locked的位置，都变成左括号的情况下，都满足左括号数量大于等于右括号数量
-
对于任意一个后缀，贪心的认为，任何非locked的位置，都变成右括号的情况下，都满足右号数量大于等于左括号数量
代码
public boolean canBeValid(String s, String locked) {// 长度为奇数，不可能是合法括号int n = s.length();if ((n & 1) == 1) {return false;}char[] chars = s.toCharArray();char[] lockedChars = locked.toCharArray();// 任意一个前缀，左括号都大于等于右括号int left = 0;for (int i = 0; i < n; i++) {if (lockedChars[i] == '1' && chars[i] == ')') {left--;} else {left++;}if (left < 0) {return false;}}// 任意一个后缀，右括号都大于等于左括号int right = 0;for (int i = n - 1; i >= 0; i--) {if (lockedChars[i] == '1' && chars[i] == '(') {right--;} else {right++;}if (right < 0) {return false;}}return true;
}
耗时
