1021. 删除最外层的括号

• 标签：栈、字符串
• 难度：简单

题目链接

• 1021. 删除最外层的括号 - 力扣

题目大意

描述：有效括号字符串为空 ""、"(" + $A$ + ")" 或 $A + B$ ，其中 $A$ 和 $B$ 都是有效的括号字符串，$+$ 代表字符串的连接。

• 例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 $s$ 非空，且不存在将其拆分为 $s = A + B$ 的方法，我们称其为原语（primitive），其中 $A$ 和 $B$ 都是非空有效括号字符串。

给定一个非空有效字符串 $s$，考虑将其进行原语化分解，使得：$s = P_1 + P_2 + ... + P_k$，其中 $P_i$ 是有效括号字符串原语。

要求：对 $s$ 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 $s$。

说明：

• $1 \le s.length \le 10^5$。
• $s[i]$ 为 '(' 或 ')'。
• $s$ 是一个有效括号字符串。

示例：

• 示例 1：

输入：s = "(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

• 示例 2：

输入：s = "(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

解题思路

思路 1：计数遍历

题目要求我们对 $s$ 进行原语化分解，并且删除分解中每个原语字符串的最外层括号。

通过观察可以发现，每个原语其实就是一组有效的括号对（左右括号匹配时），此时我们需要删除这组有效括号对的最外层括号。

我们可以使用一个计数器 $cnt$ 来进行原语化分解，并删除每个原语的最外层括号。

当计数器遇到左括号时，令计数器 $cnt$ 加 $1$，当计数器遇到右括号时，令计数器 $cnt$ 减 $1$。这样当计数器为 $0$ 时表示当前左右括号匹配。

为了删除每个原语的最外层括号，当遇到每个原语最外侧的左括号时（此时 $cnt$ 必然等于 $0$，因为之前字符串为空或者为上一个原语字符串），因为我们不需要最外层的左括号，所以此时我们不需要将其存入答案字符串中。只有当 $cnt > 0$ 时，才将其存入答案字符串中。

同理，当遇到每个原语最外侧的右括号时（此时 $cnt$ 必然等于 $1$，因为之前字符串差一个右括号匹配），因为我们不需要最外层的右括号，所以此时我们不需要将其存入答案字符串中。只有当 $cnt > 1$ 时，才将其存入答案字符串中。

具体步骤如下：

1. 遍历字符串 $s$。
2. 如果遇到 '('，判断当前计数器是否大于 $0$：
   1. 如果 $cnt > 0$，则将 '(' 存入答案字符串中，并令计数器加 $1$，即：cnt += 1。
   2. 如果 $cnt == 0$，则令计数器加 $1$，即：cnt += 1。
3. 如果遇到 ')'，判断当前计数器是否大于 $1$：
   1. 如果 $cnt > 1$，则将 ')' 存入答案字符串中，并令计数器减 $1$，即：cnt -= 1。
   2. 如果 $cnt == 1$，则令计数器减 $1$，即：cnt -= 1。
4. 遍历完返回答案字符串 $ans$。

思路 1：代码

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        cnt, ans = 0, ""
        
        for ch in s:
            if ch == '(':
                if cnt > 0:
                    ans += ch
                cnt += 1
            else:
                if cnt > 1:
                    ans += ch
                cnt -= 1
            
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为字符串 $s$ 的长度。
• 空间复杂度：$O(n)$。