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

蒙奇D索隆

发布于 2025-03-24 10:42:28

1850

文章被收录于专栏：蒙奇D索隆的学习笔记蒙奇D索隆的学习笔记

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 解释：

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"时，我们则可以将其变为"((()))"，此时该字符串又变为了有效字符串。

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

方法一：栈

在这个问题中出现了两种类型的字符——可变括号与不可变括号：

可变括号只要数量为偶数，即可全部匹配
不可变括号只能进行'('与')'匹配

因此我们不妨通过维护两个栈stack1与stack2来完成两类括号的匹配工作：

stack1用于维护不可变字符，记录所有不可变字符对应下标
stack2用于维护可变字符，记录所有可变字符对应下标

我们通过从左往右遍历字符串s的方式完成括号的匹配工作，括号的匹配规则如下：

不可变左括号'('只能与其右侧的右括号')'完成匹配
不可变右括号')'只能与其左侧的左括号'('完成匹配
可变括号可以与其左侧的左括号'('完成匹配
可变括号可以与其右侧的右括号')'完成匹配

为了确保所有括号都能够正常匹配，因此我们通过先完成不可变括号的匹配工作，再处理可变括号和剩余不可变括号的匹配工作。

处理步骤：

遇到可变括号时，在stack2中记录该括号的下标，即该元素下标入栈；
遇到不可变括号时：
- 当括号为'('，该元素下标入栈
- 当括号为')'：
  - 若栈非空，则栈顶元素出栈
  - 若栈为空，则该元素下标入栈
完成字符串中所有元素的记录

当元素全部记录完，此时stack1中都是由不可变且未完成匹配的元素，stack2中全部为可变元素；

接下来我们继续完成剩余不可变元素的匹配工作：

通过n来记录可变字符无法与不可变字符完成匹配的数量
使用key1与key2来记录stack1与stack2栈顶元素的下标
判断s[key1]的括号方向以及key1与key2的大小：
- 当s[key1] == ')' 且 key1 > key2时，能匹配成功，此时双栈栈顶元素出栈
- 当s[key1] == '(' 且 key1 < key2时，能匹配成功，此时双栈栈顶元素出栈
- 否则匹配失败，记录失败的可变字符个数，stack2栈顶元素出栈

这一阶段的匹配完成后，我们通过stack1与stack2的情况来判断是否全部匹配：

如果stack1为空栈，则说明不可变字符全部完成匹配，否则匹配失败
如果stack2中剩余字符数量和n记录的数量之和为偶数，则可变字符全部完成匹配，否则匹配失败

当可变字符与不可变字符同时完成匹配，该字符串才为有效字符串，否则无效；

编写代码

方法一：栈

C语言

//判断是否需要入栈
bool Need_Push(char* s, int* stack, int i, int top) {
    // 栈为空
    bool flag1 = top == 0;
    bool flag2 = false;
    bool flag3 = false;
    // 匹配失败
    if (!flag1) {
        // 新元素与栈顶元素相等
        flag2 = s[stack[top - 1]] == s[i];
        // 栈顶为左括号，新元素为右括号
        flag3 = s[stack[top - 1]] == ')' && s[i] == '(';
    }
    return flag1 || flag2 || flag3;
}

bool canBeValid(char* s, char* locked) {
    int len = strlen(s);
    int* stack1 = (int*)calloc(len, sizeof(int));
    assert(stack1);
    int top1 = 0;
    int* stack2 = (int*)calloc(len, sizeof(int));
    assert(stack2);
    int top2 = 0;
    for (int i = 0; i < len; i++) {
        // 不可变
        if (locked[i] == '1') {
            if (Need_Push(s, stack1, i, top1)) {
                stack1[top1] = i;
                top1 += 1;
            }
            else {
                top1 -= 1;
            }
        }
        // 可变
        else {
            stack2[top2] = i;
            top2 += 1;
        }
    }
    int n = 0;
    while (top1 && top2) {
        int key1 = stack1[top1 - 1], key2 = stack2[top2 - 1];
        // 不可变栈，栈顶为左括号，可变栈栈顶元素位于不可变栈左侧
        bool flag1 = s[key1] == ')' && key2 < key1;
        // 不可变栈，栈顶为右括号，可变栈栈顶元素位于右侧
        bool flag2 = s[key1] == '(' && key2 > key1;
        // 匹配成功
        if (flag1 || flag2) {
            top1 -= 1;
        }
        else {
            // 记录可变栈中元素未与不可变栈中元素匹配成功的个数
            n += 1;
        }
        top2 -= 1;
    }
    free(stack1);
    free(stack2);
    n += top2;
    return top1 == 0 && n % 2 == 0;
}

Python

class Solution(object):
    def canBeValid1(self, s, locked):
        """
        :type s: str
        :type locked: str
        :rtype: bool
        """
        len1 = len(s)
        stack1 = []     # 不可变字符栈 
        top1 = 0
        stack2 = []     # 可变字符栈
        top2 = 0
        for i in range(len1):
            if locked[i] == '1':
                # 非空栈，并且匹配成功，执行出栈操作
                if top1 and s[i] == ')' and s[stack1[top1-1]] == '(':
                    stack1.pop()
                    top1 -= 1
                # 空栈，或者匹配失败，入栈
                else:
                    stack1.append(i)
                    top1 += 1
            else:
                stack2.append(i)
                top2 += 1
        n = 0
        while top1 and top2:
            key1 = stack1[top1 - 1]
            key2 = stack2[top2 - 1]
            # 匹配成功，出栈
            if (s[key1] == ')' and key2 < key1) or (s[key1] == '(' and key2 > key1):
                stack1.pop()
                top1 -= 1
            # 匹配失败，记录字符数量
            else:
                n += 1
            stack2.pop()
            top2 -= 1
        n += top2
        return top1 == 0 and n % 2 == 0

代码测试

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

可以看到，我们正常的通过了所有的测试用例。下面我们继续测试Python：

可以看到，我们同样通过了Python的所有测试用例。

算法分析

下面我们就来分析一下方法一的时间复杂度与空间复杂度，这里我们以C语言代码为例；

时间复杂度

在整个算法中，总共有两个循环，在第一个for循环中，存在一次函数调用。

首先我们来看一下调用的函数里面的时间复杂度：

//判断是否需要入栈
bool Need_Push(char* s, int* stack, int i, int top) {
    // 栈为空
    bool flag1 = top == 0;									//O(1)
    bool flag2 = false;										//O(1)
    bool flag3 = false;										//O(1)
    // 匹配失败
    if (!flag1) {											//O(1)
        // 新元素与栈顶元素相等
        flag2 = s[stack[top - 1]] == s[i];					//O(1)
        // 栈顶为左括号，新元素为右括号
        flag3 = s[stack[top - 1]] == ')' && s[i] == '(';	//O(1)
    }
    return flag1 || flag2 || flag3;							//O(1)
}

在该函数中并不存在任何循环，因此函数的时间复杂度为O(1)。接下来我们就来看剩下的两个循环：

    for (int i = 0; i < len; i++) {					//O(N)
        // 不可变
        if (locked[i] == '1') {						//O(1)
            if (Need_Push(s, stack1, i, top1)) {	//O(1)
                stack1[top1] = i;					//O(1)
                top1 += 1;							//O(1)
            }
            else {									//O(1)
                top1 -= 1;							//O(1)
            }
        }
        // 可变
        else {										//O(1)
            stack2[top2] = i;						//O(1)
            top2 += 1;								//O(1)
        }
    }
    int n = 0;										//O(1)
    while (top1 && top2) {							//O(M)
        int key1 = stack1[top1 - 1], key2 = stack2[top2 - 1];//O(1)
        // 不可变栈，栈顶为左括号，可变栈栈顶元素位于不可变栈左侧
        bool flag1 = s[key1] == ')' && key2 < key1;			//O(1)
        // 不可变栈，栈顶为右括号，可变栈栈顶元素位于右侧
        bool flag2 = s[key1] == '(' && key2 > key1;			//O(1)
        // 匹配成功
        if (flag1 || flag2) {								//O(1)
            top1 -= 1;										//O(1)
        }
        else {												//O(1)
            // 记录可变栈中元素未与不可变栈中元素匹配成功的个数
            n += 1;											//O(1)
        }
        top2 -= 1;											//O(1)
    }

在这两个循环中，第一个循环的时间复杂度为O(N)，第二个循环的时间复杂度为O(M)，其中 M <= N，因此总的时间复杂度为O(N)。

空间复杂度

在该算法中，涉及额外空间的就是栈空间的申请：

    int* stack1 = (int*)calloc(len, sizeof(int));						//O(N)
    assert(stack1);
    int top1 = 0;
    int* stack2 = (int*)calloc(len, sizeof(int));						//O(N)
    assert(stack2);
    int top2 = 0;

在算法中，我们申请了两个长度为len的栈空间，空间的数量随着len的变化而改变，因此其对应的空间复杂都均为O(N)，因此总的空间复杂度为:

O(N)+O(N)=O(N)