[LeetCode] 每日一题 2116. 判断一个括号字符串是否有效（冗余假设法）

题目链接

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

题目描述

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

• 字符串为 ().

• 它可以表示为 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 变为有效字符串。

示例 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' 。

解题思路

我们可以假设字符串可以通过变更变成合法的括号字符串，并采用从左到右和从右到左的双向遍历策略：

1. 从左到右扫描：尽量将字符转换成左括号 '('，并维护一个计数 count 记录左括号的数量。如果遇到无法转换的多余右括号 ')'，直接返回 false

2. 从右到左扫描：尽量将字符转换成右括号 ')'，同样维护 count 记录右括号的数量。如果遇到无法转换的多余左括号 '('，返回 false

3. 若两个方向的扫描都通过，说明字符串有足够的冗余量，可以修改成合法括号字符串，返回 true

这个方法利用了冗余假设：假设可以自由转换 locked[i] == '0' 的括号，使得括号匹配，并通过两次遍历保证最终的合法性

代码实现

class Solution {
    public boolean canBeValid(String s, String locked) {
        if (s.length() % 2 != 0) {
            return false;
        }
        int count = 0;
        char[] sCharArray = s.toCharArray();
        for (int i = 0; i < sCharArray.length; i++) {
            if (sCharArray[i] == ')') {
                if (locked.charAt(i) == '0') {
                    sCharArray[i] = '(';
                    count++;
                } else {
                    count--;
                    if (count < 0) {
                        return false;
                    }
                }
            } else {
                count++;
            }
        }
        count = 0;
        for (int i = sCharArray.length - 1; i >= 0; i--) {
            if (sCharArray[i] == '(') {
                if (locked.charAt(i) == '0') {
                    sCharArray[i] = ')';
                    count++;
                } else {
                    count--;
                    if (count < 0) {
                        return false;
                    }
                }
            } else {
                count++;
            }
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：O(n)，我们进行了两次线性遍历，每次遍历的操作都是 O(1)，总计 O(2n) ≈ O(n)。

• 空间复杂度：O(n)，由于 sCharArray 复制了字符串 s，所以额外的空间占用是 O(n)。如果不进行字符数组转换，而是直接使用 charAt，可以优化为 O(1)

总结

本题的核心在于利用冗余括号的假设，通过双向遍历确保在所有可修改的情况下，是否能调整为合法括号字符串。这种方法有效地处理了括号匹配问题，避免了复杂的回溯或动态规划

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。