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

难度: Medium

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

字符串为 ().
它可以表示为 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 <= 10⁵
s[i] 要么是 '(' 要么是 ')' 。
locked[i] 要么是 '0' 要么是 '1' 。

Submission

运行时间: 100 ms

内存: 20.9 MB

class Solution:
    def canBeValid(self, s: str, locked: str) -> bool:
        n=len(s)
        left=[]
        star=[]
        i=0
        while i<n:
            if locked[i]=='0':
                star.append(i)
            else:
                if s[i]=='(':
                    left.append(i)
                else:
                    if len(left):
                        left.pop()
                    else:
                        if len(star):
                            star.pop()
                        else:
                            return False
            i+=1
        
        while len(left) and len(star):
            i=left[-1]
            j=star[-1]
            left.pop()
            star.pop()
            if i>j:return False
        if len(star)==0:
            return len(left)==0
        else:
            return len(star)%2==0

Explain

这个题解首先遍历一次输入字符串s，同时记录每个可以变换的字符位置（'0' in locked）到star列表，以及左括号的位置到left列表。如果当前位置锁定且为右括号，则尝试匹配一个未匹配的左括号或可变字符；如果两者都匹配不到，则直接返回false。第二次遍历在遍历结束后，处理剩余的left和star。如果left中的左括号索引在star中任何可变字符的索引之前，即无法用可变字符匹配成对的括号，那么返回false。如果star列表中还有剩余的可变字符，只要数量是偶数，就可以配对成功，否则返回false。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def canBeValid(self, s: str, locked: str) -> bool:
        n = len(s)
        left = []
        star = []
        i = 0
        while i < n:
            if locked[i] == '0':
                star.append(i)
            else:
                if s[i] == '(':
                    left.append(i)
                else:
                    if len(left):
                        left.pop()
                    else:
                        if len(star):
                            star.pop()
                        else:
                            return False
            i += 1
        
        while len(left) and len(star):
            i = left[-1]
            j = star[-1]
            if i > j:
                return False
            left.pop()
            star.pop()
        if len(star) == 0:
            return len(left) == 0
        else:
            return len(star) % 2 == 0

Explore

在第一次遍历中，算法尝试立即匹配每个遇到的右括号，无论是锁定的还是可变的。如果右括号是锁定的且无法立即匹配，则算法返回false。在这一阶段，所有可以立即被匹配的左括号都会被消耗掉。第二次遍历处理剩余的未匹配的左括号和可变字符，通过从后向前比较left和star列表中的索引，确保每个左括号都试图与其后的一个可变字符匹配。此方法确保了所有可能的匹配方式都被尝试，因为它考虑了所有剩余的左括号，并尽可能使用后面的可变字符进行匹配。

这个逻辑基于有效括号序列的要求，即每个左括号必须有一个相应的右括号来匹配。在算法的上下文中，`star`列表中的索引代表可以变成右括号的位置。如果要匹配的左括号的位置在一个可变成右括号的位置之前，那么在这个左括号之前就没有其他字符可以转变成匹配的右括号了，因此无法形成有效的匹配对。由此，如果left列表中有任何左括号的索引在star列表中对应的可变字符索引之前，就意味着这个左括号无法被匹配，因此算法返回false。

在括号匹配问题中，每个左括号都需要对应一个右括号才能形成有效的匹配对。如果`star`列表中剩余的可变字符数量是偶数，这意味着可以把这些字符平均分成两半，其中一半变成左括号，另一半变成右括号，从而形成完整的匹配对。例如，如果有四个剩余的`star`，可以将其中两个变为左括号，两个变为右括号，从而形成两对有效的括号。如果`star`的数量是奇数，则无法完全配对，因为会始终剩下一个无法匹配的括号。