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^5
  • s[i] 是 ‘(’ 或 ‘)’
  • locked[i] 是 ‘0’ 或 ‘1’

解题思路

这个问题可以用贪心算法解决。关键思路是分两次遍历：

核心观察：

  1. 奇数长度的字符串永远不可能构成有效括号串
  2. 固定的 ‘)’ 必须有对应的 ‘(’ 来匹配，优先使用固定的 ‘(’，其次使用可变位置
  3. 剩余的固定 ‘(’ 需要用可变位置来平衡

算法步骤：

  1. 第一次从左到右遍历：处理所有固定的 ‘)’

    • 遇到固定的 ‘(’ 或可变位置时，计数器加1（可以用来匹配后续的 ‘)’）
    • 遇到固定的 ‘)’ 时，如果没有可用的匹配（计数器为0），返回false；否则计数器减1

  2. 第二次从右到左遍历：处理剩余的固定 ‘(’

    • 重新计算可变位置和固定 ‘)’ 的数量
    • 遇到固定的 ‘(’ 时，如果没有足够的位置来匹配，返回false

这种方法确保了：

  • 所有固定的 ‘)’ 都能找到匹配
  • 所有固定的 ‘(’ 都能被平衡
  • 剩余的可变位置数量为偶数（可以配对）

时间复杂度O(n)，空间复杂度O(1)。

代码实现

class Solution {
public:
    bool canBeValid(string s, string locked) {
        int n = s.length();
        if (n % 2 == 1) return false;
        
        // 第一次遍历：从左到右，处理固定的 ')'
        int balance = 0;
        for (int i = 0; i < n; i++) {
            if (locked[i] == '0' || s[i] == '(') {
                balance++;
            } else {  // locked[i] == '1' && s[i] == ')'
                balance--;
                if (balance < 0) return false;
            }
        }
        
        // 第二次遍历：从右到左，处理固定的 '('
        balance = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (locked[i] == '0' || s[i] == ')') {
                balance++;
            } else {  // locked[i] == '1' && s[i] == '('
                balance--;
                if (balance < 0) return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def canBeValid(self, s: str, locked: str) -> bool:
        n = len(s)
        if n % 2 == 1:
            return False
        
        # 第一次遍历：从左到右，处理固定的 ')'
        balance = 0
        for i in range(n):
            if locked[i] == '0' or s[i] == '(':
                balance += 1
            else:  # locked[i] == '1' and s[i] == ')'
                balance -= 1
                if balance < 0:
                    return False
        
        # 第二次遍历：从右到左，处理固定的 '('
        balance = 0
        for i in range(n - 1, -1, -1):
            if locked[i] == '0' or s[i] == ')':
                balance += 1
            else:  # locked[i] == '1' and s[i] == '('
                balance -= 1
                if balance < 0:
                    return False
        
        return True

public class Solution {
    public bool CanBeValid(string s, string locked) {
        int n = s.Length;
        if (n % 2 == 1) return false;
        
        // 第一次遍历：从左到右，处理固定的 ')'
        int balance = 0;
        for (int i = 0; i < n; i++) {
            if (locked[i] == '0' || s[i] == '(') {
                balance++;
            } else {  // locked[i] == '1' && s[i] == ')'
                balance--;
                if (balance < 0) return false;
            }
        }
        
        // 第二次遍历：从右到左，处理固定的 '('
        balance = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (locked[i] == '0' || s[i] == ')') {
                balance++;
            } else {  // locked[i] == '1' && s[i] == '('
                balance--;
                if (balance < 0) return false;
            }
        }
        
        return true;
    }
}

var canBeValid = function(s, locked) {
    const n = s.length;
    if (n % 2 === 1) return false;
    
    // Forward pass: check if we can balance with enough opening brackets
    let balance = 0;
    let flexible = 0;
    
    for (let i = 0; i < n; i++) {
        if (locked[i] === '0') {
            flexible++;
        } else if (s[i] === '(') {
            balance++;
        } else { // s[i] === ')' and locked[i] === '1'
            balance--;
        }
        
        // If we have more closing than opening + flexible, impossible
        if (balance + flexible < 0) return false;
    }
    
    // Backward pass: check if we can balance with enough closing brackets
    balance = 0;
    flexible = 0;
    
    for (let i = n - 1; i >= 0; i--) {
        if (locked[i] === '0') {
            flexible++;
        } else if (s[i] === ')') {
            balance++;
        } else { // s[i] === '(' and locked[i] === '1'
            balance--;
        }
        
        // If we have more opening than closing + flexible, impossible
        if (balance + flexible < 0) return false;
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值
时间复杂度O(n)
空间复杂度O(1)

相关题目