今日题目

https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid/

解题思路

要构造合法的括号字符串，需要为每个 ‘)’ 在其左侧找到对应的 ‘(’，并为每个 ‘(’ 在其右侧找到对应的 ‘)’。 从左到右遍历时，我们可以先满足第一个条件。

当遇到 ‘)’ 时，有三种方式为其匹配 ‘(’：一是已有的 ‘(’，二是找一个未锁定的 ‘)’，三是如果 ‘)’ 本身是未锁定的，可以将其转换为 ‘(’。

假设我们已为所有 ‘)’ 找到了匹配的 ‘(’，接下来需要为剩余的 ‘(’ 找到对应的 ‘)’。此时唯一的办法是找一个未锁定的括号，因为所有 ‘)’ 已经被匹配完毕。

解题方案

首先，若字符串长度为奇数，则永远无法构成合法括号字符串，直接 return False。

维护两个数组：$anyBracket$ 存储所有未锁定括号的下标，$openBracket$ 存储所有 ‘(’ 的下标。

从左到右遍历整个字符串，会遇到以下几种情况：

  1. 当前字符是未锁定的括号：将其下标压入 $anyBracket$ 栈。
  2. 当前字符是 ‘(’：将其下标压入 $openBracket$ 栈。
  3. 当前字符是 ‘)’：需要为其找到一个 ‘(’。
    • 优先从 $openBracket$ 栈中弹出一个 ‘(’，这样同时完成了为 ‘(’ 寻找 ‘)’ 的任务。
    • 若 $openBracket$ 栈为空，则从 $anyBracket$ 栈中取出一个未锁定的括号（充当 ‘(’）。
    • 若两个栈均为空，则 return False，因为无法为当前 ‘)’ 找到匹配的 ‘(’。

遍历结束后，$openBracket$ 中可能还剩下未匹配的 ‘(’。

此时遍历 $openBracket$ 中每个未匹配的 ‘(’，检查 $anyBracket$ 中是否存在下标更大的括号（即位于其右侧的未锁定括号）。

  • 若存在，说明成功为其找到了 ‘)’，匹配成功！
  • 否则无法匹配，return False。

若 $anyBracket$ 中剩余元素个数为偶数（由于前面已做奇偶性检验，这里必然成立），则 return True，大功告成！

重要技巧

  • 为什么 $openBracket$ 和 $anyBracket$ 都要用栈？
  • 因为 ‘)’ 总是优先与其左侧最近的 ‘(’ 匹配，因此需要先进先出（FIFO）的数据结构来获取"最近的元素"。

复杂度分析

  • 时间复杂度：$O(N)$，N 为字符串长度。

  • 空间复杂度：$O(N)$，存储了各括号的下标。

代码

class Solution:
    def canBeValid(self, s: str, locked: str) -> bool:
        if len(s) % 2 == 1:
            return False
        
        openBracket = []
        anyBracket = []

        for i in range(len(s)):
            if locked[i] == '0':
                anyBracket.append(i)
            else:
                if s[i] == '(':
                    openBracket.append(i)
                else:
                    if len(openBracket) > 0:
                        openBracket.pop()
                    elif len(anyBracket) > 0:
                        anyBracket.pop()
                    else:
                        return False
        
        if len(anyBracket) < len(openBracket):
            return False

        idx = len(anyBracket) - 1
        for i in range(len(openBracket) - 1, -1, -1):
            if anyBracket[idx] < openBracket[i]:
                return False
            idx -= 1
        
        return idx % 2 == 1

image.png