【LeetCode】括号问题——2116. 判断一个括号字符串是否有效（解法二）

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

相关标签：栈、贪心、字符串 题目难度：中等 题目描述 一个括号字符串是只由 '(' 和 ')' 组成的 非空 字符串。 如果一个字符串满足下面 任意 一个条件，那么它就是有效的：

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

示例1

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 <= 10^5
• s[i] 要么是 '(' 要么是 ')' 。
• locked[i] 要么是 '0' 要么是 '1' 。

解题思路

题目解析

在字符串匹配中有一个核心思路：

• 对于一个有效字符串"()"而言，其左右括号的数量一定相等

从这个思路出发，当我们来判断一个字符串是否为有效字符串，我们只需要判断其左右字符的个数是否相等。即当一个字符串为")))((("，那我们可以判定它为有效字符串。

在这个基础上，由于不同题目的限制，我们需要知道在本题中怎样才是匹配成功，怎么样是匹配失败：

• 左括号'('只能与其右侧的右括号')'完成匹配
• 右括号')'只能与其左侧的左括号'('完成匹配

在这个规则上如果我们再来看该字符串")))((("，此时我们会发现，虽然左括号与右括号的数量一致，但是他们都没有能够正常与之匹配的括号，因此该字符串为无效字符串。

在本题中，还给出了一个条件，对于每个字符，都会通过'0'与'1'来记录其是否可以改变，那也就是说，还是这个字符串")))((("，当它对应的locked值为"000000"时，我们则可以将其变为"((()))"，此时该字符串又变为了有效字符串。

接下来我们就需要判断一个给定的字符串是否为有效字符串，有两种解题思路——栈、数学。在今天的内容中，我们会介绍第二种解题思路——数学。

方法二：数学

判断一个字符串是否为有效字符串，实际上就是在字符串中查找是否存在无法完成匹配的括号。

这里我们不妨设左括号为1，右括号为-1，当一个字符串为有效字符串时，其字符串中所有括号之和一定为0。若和非0，那一定存在无法匹配的括号：

• 字符串之和大于0，则存在无法匹配的左括号'('
• 字符串之和小于0，则存在无法匹配的右括号')'

在本题中，一个括号要想正常完成匹配，那么左括号'('一定位于左侧，右括号')'一定位于右侧。

这里我们引入有效前缀字符串的概念：

• 如果括号字符串的某个前缀字符串满足它本身及它的所有前缀的分数均大于等于 0，则称该前缀为有效前缀。

什么意思呢？这里我解释一下：

对于一个长度为n的括号字符串s，如果存在一个长度为i+1的前缀字符串s[0…i]，我们可以通过判断其所有括号之和的情况来判断该前缀是否有效：

• 字符串之和为0，则说明该前缀为有效字符串
• 字符串之和大于0，则说明该前缀字符串中存在无法匹配的左字符串'('
• 字符串之和小于0，则说明该前缀字符串总存在无法匹配的右字符串')'

因为此时我们求和的是字符串s中的一个前缀字符串，而前缀字符串又是从左往右获取的一个子串，那么根据其和的情况，我们可以进一步判断：

• 如果该前缀和大于0，该前缀的右侧有可能存在与其无法匹配的左括号'('相匹配的右括号')'，因此字符串s可能是一个有效字符串；
• 如果该前缀和小于0，则说明字符串s的[0…i]中存在一个无法匹配的')'，那对于[i+1…n-1]中即使存在无法匹配的左括号'('，也无法与该右括号完成匹配，即字符串s一定不是一个有效字符串；

前缀字符串.jpg

由上述内容我们不难得出结论：

• 有效字符串的任一前缀字符串都是有效前缀；

因此我们可以引入两个数组分别记录前缀中未匹配的'('以及前缀中完成匹配后还剩余的未匹配的'('个数：

• arr1——前缀中未匹配的'('总数
• arr2——匹配完后剩余的'('总数

令arr1[0] == arr2[0] == 0，即当前缀为空串时，不存在未匹配的 ( ；

在从左往右遍历字符串s的过程中，遇到的字符有3种情况：

• 不可变左括号 (——即locked[i] == '1', s[i] == '('
  • 此时 arr1[i] = arr1[i - 1] + 1
  • arr2[i] = fmax(arr2[i -1] + 1, (i + 1) % 2)
• 不可变左括号 )——即locked[i] == '1', s[i] == ')'
  • 此时 arr1[i] = arr1[i - 1] - 1
  • arr2[i] = fmax(arr2[i -1] - 1, (i + 1) % 2)
• 可变括号——即 locked[i] == '0'
  • 在记录未匹配的 '(' 时，默认可变括号为 '('，即 arr1[i] = arr1[i - 1] + 1
  • 在记录匹配完后剩余的 '(' 时，默认可变括号为 ')'，即 arr2[i] = fmax(arr2[i - 1] - 1, (i + 1) %2)

对于数组 arr1 的维护很简单，只要正常的记录字符的方向即可，这里之所以要将可变字符默认为 '(' ，是因为两点原因：

• '(' 可以在后续的遍历中寻找与之匹配的 ')'
• ')' 则无法在后续的遍历中寻找与之匹配的 '('

而对于 arr2 的维护则比较复杂，由于该数组记录的是完成匹配后剩余未匹配的 '(' 的数量，因此会存在三种情况：

• 前缀字符完全匹配，即前缀字符串中不存在未匹配的 '('，此时数量为0
• 前缀字符完全匹配，但字符串长度为单数，即存在一个没有匹配的字符，且该字符为 '('，此时数量为1
• 前缀字符不完全匹配，此时字符串中还剩 i - 1 个 '('

在前缀字符完全匹配的情况下，'(' 的数量为 (i + 1) % 2 ，这是因为对于原本长度为i的前缀字符，在遍历到新的字符后，此时的长度变成了i + 1，若完全匹配，那么只需要考虑此时前缀字符长度的奇偶性，即 (i + 1) % 2 的取值；

在不完全匹配的情况下，即原本长度为 'i' 的前缀字符串，在遇到该字符后，则需要根据该字符的具体情况进行判断：

• 当前字符为不可变 '(' ，则表示为匹配的 '(' 数量又增加了一个，因此取值为 arr2[i] = arr2[i - 1] + 1
• 当前字符为不可变 ')' ，则表示完成了一次匹配，'(' 减少了一个，因此取值为 arr2[i] = arr2[i - 1] - 1
• 当前字符为可变字符，则默认该字符为 ')'，此时会完成一次匹配，因此取值为 arr2[i] = arr2[i - 1] - 1

但是为了防止不存在未匹配的 '(' ，因此我们需要取值完全匹配时剩余未匹配 '(' 的个数和不完全匹配时剩余 '(' 的个数这二者之中的最大值：

• 当不完全匹配的值大于完全匹配的值，则说明此时的前缀字符串中执行的是不完全匹配；
• 当不完全匹配的值小于完全匹配的值，则说明此时的前缀字符串中执行的是完全匹配；

这个点需要大家反复阅读，认真理解一下完全匹配与不完全匹配。这里留给大家思考的空间，我就不再展开。

此时我们需要注意，如果 arr1[i] < arr2[i] ，这时只有一种情况——在完全匹配且'(' 的剩余数量为0的情况下，新增了一个 ')'，那此时 arr1[i] 的值一定为 -1，这时无论后续如何遍历，都不可能再找到与之匹配的括号了。因此也就不需要继续遍历了，此时我们可以直接判断该字符串不是有效字符串。

对于数组arr1与arr2，我们在实际的使用中不难发现，我们在每一次遍历中只会使用当前数组中最后一个元素的值。

从栈的角度来描述，就是每次都只会使用栈顶元素，因此我们可以将其转换成只含一个元素的栈，通过维护栈空间来进行判断。

当然，我们还可以进一步将其简化成记录栈顶元素的指针，因此这里我们采用两个栈顶指针来记录 '(' 的数量：

• top1——记录当前 '(' 的数量
• top2——记录完成匹配后 '(' 的剩余数量

在记录 top2 时，我们总是取未完全匹配时 '(' 的剩余数量与完全匹配时 '(' 的剩余数量这二者之中的最大值，即：

top2 = fmax(top2 + diff, (i + 1) % 2)

其中，diff 的取值与括号的类型有关：

• 括号为不可变 '('——diff = 1
• 括号为不可变 ')' 或可变括号——diff = -1

下面我们就可以进行代码编写了；

编写代码

方法二：数学

首先我们还是通过C语言编写代码：

C语言

//方法二：数学
bool canBeValid(char* s, char* locked) {
    int len = strlen(s);
    int top1 = 0, top2 = 0;
    for (int i = 0; i < len; i++) {
        if (locked[i] == '1') {
            int diff = 0;
            if (s[i] == '(') {
                diff = 1;
            }
            else {
                diff = -1;
            }
            top1 += diff;
            top2 = fmax(top2 + diff, (i + 1) % 2);
        }
        else {
            top1 += 1;
            top2 = fmax(top2 - 1, (i + 1) % 2);
        }
        if (top1 < top2) {
            return false;
        }
    }
    return !top2;
}

接下来我们继续编写Python代码：

Python

class Solution(object):
    def canBeValid(self, s, locked):
        """
        :type s: str
        :type locked: str
        :rtype: bool
        """
        len1 = len(s)
        # top1：全部未匹配，top2：全部匹配
        top1, top2 = 0, 0
        for i in range(len1):
            # 不可变字符
            if locked[i] == '1':
                diff = 0    # 括号值：左括号，长度增加，右括号，长度减少
                # 左括号
                if s[i] == '(':
                    diff = 1
                else:
                    diff = -1
                top1 += diff    # 改变子串最长未匹配长度
                top2 = max(top2 + diff, (i + 1) % 2)    # 子串全部完成匹配的最小长度
            # 可变字符
            else:
                top1 += 1   # 默认可变字符为左括号
                top2 = max(top2 - 1, (i + 1) % 2)
            # 当未匹配的长度小于完成匹配的最小长度时，说明此时的子串中存在无法匹配的字符
            if top1 < top2:
                return False
        # top2 == 0 表示字符串全部完成匹配，否则存在无法匹配的字符
        return top2 == 0

代码测试

我们首先将写好的C语言代码复制到力扣中进行测试：

C语言测试

C语言测试.png

可以看到很好的通过了全部的测试用例。接下来我们就来测试Python代码：

Python测试

Python测试.png

可以看到此时也很好的通过了全部用例。

算法分析

这里我们还是从时间复杂度与空间复杂度的角度分析代码，同样还是借助C语言代码完成分析；

时间复杂度

我们同样还是逐步分析整个代码：

//方法二：数学
bool canBeValid(char* s, char* locked) {
    int len = strlen(s);							//O(N)
    int top1 = 0, top2 = 0;							//O(1)
    for (int i = 0; i < len; i++) {					//O(N)
        if (locked[i] == '1') {						//O(1)
            int diff = 0;							//O(1)
            if (s[i] == '(') {						//O(1)
                diff = 1;							//O(1)
            }
            else {									//O(1)
                diff = -1;							//O(1)
            }
            top1 += diff;							//O(1)
            top2 = fmax(top2 + diff, (i + 1) % 2);	//O(1)
        }
        else {										//O(1)
            top1 += 1;								//O(1)
            top2 = fmax(top2 - 1, (i + 1) % 2);		//O(1)
        }
        if (top1 < top2) {							//O(1)
            return false;							//O(1)
        }
    }
    return !top2;									//O(1)
}

在介绍解法一时，我主要介绍了两个循环部分的时间复杂度，没有介绍计算字符串长度的时间复杂度，刚好借助今天来说明一下理由为什么可以忽略计算字符串长度的时间复杂度。

从上面的逐步分析我们不难发现，整个算法的时间复杂度为：

O(N) + O(1) + O(N) + 12 * O(1) = 2 * O(N) + 12 * O(1) = O(N)

对于同一个数量级的时间复杂度，我们只需要计算1次即可，毕竟到最后都只会取数量级最大的那部分时间复杂度，且其系数会改写成1。因此在上一篇内容中，我们主要介绍了循环部分的时间复杂度。

空间复杂度

在此方法中我们并没有进行任何额外空间的申请，因此空间复杂度为 O(1)。

小结

本题的算法评估结果为：

• 时间复杂度：O(N)
• 空间复杂度：O(1)

在此解法中，我们从数学的角度来分析并解答了该问题，相比于解法一，我们在空间复杂度上进行了显著的提升，由原先的 O(N) 提升至了 O(1)。

不过相比于栈的解法，此解法在理解上会复杂一点，如果大家只是追求解题的话，可以采用栈的求解方法，简单且容易理解；如果大家对算法效率有有一定的要求，可以尝试着通过数学的方式实现。