西宁做网站多少钱_搜狗推广怎么样_免费找精准客户软件_网店推广方案策划书

问题背景

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

• 字符串为 $()$。
• 它可以表示为 $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$。

数据约束

• $n=s.length=locked.length$
• $1\le n\le 10^5$
• $s[i]$ 要么是 ‘(’ 要么是 ‘)’ 。
• $locked[i]$ 要么是 ‘0’ 要么是 ‘1’ 。

解题过程

括号匹配的字符串，任意前缀中左括号的数量都应不少于右括号的数量，允许改变括号类型的位置可以视为未知进行讨论。
实际上只要未匹配的左括号数量始终不为负，且最终能减少到零，就说能够将这个字符串修改为有效字符串。

具体实现

class Solution {public boolean canBeValid(String s, String locked) {int n = s.length();if ((n & 1) == 1) {return false;}int max = 0;int min = 0;for (int i = 0; i < n; i++) {if (locked.charAt(i) == '1') {int cur = s.charAt(i) == '(' ? 1 : -1;max += cur;if (max < 0) {return false;}min += cur;} else {max++;min--;}if (min < 0) {min = 1;}}return min == 0;}
}