LeetCode2116

发表于 更新于 分类于 ， 本文字数： 1.4k 阅读时长 ≈ 5 分钟

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

​ 通宵一夜之后上午边吃早饭边写的这道题。看到括号，配对类的很明显是要求前缀和了，这道题和前几天做的LeetCode.1963很像,不过那一道用双指针，感觉比这一道题简单一点。

题目描述

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

字符串为 ().
它可以表示为 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：

1
2
3
4
输入：s = "))()))", locked = "010100"
输出：true
解释：locked[1] == '1' 和 locked[3] == '1' ，所以我们无法改变 s[1] 或者 s[3] 。
我们可以将 s[0] 和 s[4] 变为 '(' ，不改变 s[2] 和 s[5] ，使 s 变为有效字符串。

示例2：

1
2
3
输入：s = "()()", locked = "0000"
输出：true
解释：我们不需要做任何改变，因为 s 已经是有效字符串了。

示例3：

1
2
3
4
输入：s = ")", locked = "0"
输出：false
解释：locked 允许改变 s[0] 。
但无论将 s[0] 变为 '(' 或者 ')' 都无法使 s 变为有效字符串。

示例4：

1
2
3
4
输入：s = "(((())(((())", locked = "111111010111"
输出：true
解释：locked 允许我们改变 s[6] 和 s[8]。
我们将 s[6] 和 s[8] 改为 ')' 使 s 变为有效字符串。

提示：

1
2
3
4
n == s.length == locked.length
1 <= n <= 105
s[i] 要么是 '(' 要么是 ')' 。
locked[i] 要么是 '0' 要么是 '1' 。

官方题解

​ 拿到字符串第一件事就是把（转换成1，把）转换成-1，这样才能适应求前缀和的方法。然后根据 有效括号字符串 的定义，其实就是括号能配上对，我们可以知道一个括号字符串有效用前缀和来表示就是该字符串总的分数为0，且任意一个位置前缀和都大于等于0。

​ 官方题解说让自行尝试证明，我反正搞不懂咋证明，我一开始看了一眼相关标签，里面明明白白写着个栈，我就在那入栈出栈捣鼓半天，也不知道是智力不够还是通宵通的反正搞不懂。

​ 说回来，题解在这里给出了一个 有效前缀 的定义，就是说一个字符串的某个前缀字符串满足它本身以及它所有的前缀的分数均大于等于零，则称该前缀为有效前缀。相对于 有效括号字符串 来说，将定义放宽至了其本身的分数可以大于零。

​ 然后对字符串 s 定义最大有效分数mx和最小有效分数mn，具体地：

  • mx代表前缀s[0...i]可以达到的最大分数。

  • mn代表前缀s[0...i]可以到达的最小分数以及作为有效前缀所需的最小分数的二者的较大值。

​ 其中 作为有效前缀所需的最小分数 的取值，由于字符串长度的奇偶一定和其最小前缀和的奇偶性相同，故而取值不是0就是1，即为(i+1)mod2。当i=0时，有mx = mn = 0。
​ 然后从左至右遍历字符串s，维护mx和mn数组的当前值，我们可以知道在当前的mx和mn的值满足条件的情况下，其前缀一定满足条件，故而不需要去维护整个数组。
​ 根据locked[i]的取值，可以获得以下情况：

1
2
locked[i] = 1, 此时s[i]无法更改。因此mx = mx + diff, 其中diff为s[i]的分数。同理，mn = max(mn+diff, (i+1)mod2)。
locked[i] = 0, 此时s[i]可以更改。因此mx = mx + 1，且mn = max(mn-1, (i+1)mod2)。

​ 遍历过程中，若是出现某一下标i有mx<mn，则s[0...i]无法通过变换成为有效前缀，即s无法通过变换成为 有效括号字符串 ，此时返回false。
​ 遍历结束后，只需要确定s是否可以通过变换使得分数为0即可。假定s长度为n，这等价于判断mn是否为0，如果mn=0，则s可以通过变换成为 有效括号字符串 ，返回true，否则返回false。

最终代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public boolean canBeValid(String s, String locked) {
        int n = s.length();
        int mx = 0;   // 可以达到的最大分数
        int mn = 0;   // 可以达到的最小分数 与 最小有效前缀对应分数 的较大值
        for (int i = 0; i < n; ++i) {
            if (locked.charAt(i) == '1') {
                // 此时对应字符无法更改
                int diff;
                if (s.charAt(i) == '(') {
                    diff = 1;
                } else {
                    diff = -1;
                }
                mx += diff;
                mn = Math.max(mn + diff, (i + 1) % 2);
            } else {
                // 此时对应字符可以更改
                ++mx;
                mn = Math.max(mn - 1, (i + 1) % 2);
            }
            if (mx < mn) {
                // 此时该前缀无法变为有效前缀
                return false;
            }
        }
        // 最终确定 s 能否通过变换使得分数为 0（成为有效字符串）
        return mn == 0;
   
    }
}