跳转至

LeetCode: 1021. 删除最外层的括号

1、题目描述

有效括号字符串为空 ("")"(" + A + ")"A + B,其中AB 都是有效的括号字符串,+ 代表字符串的连接。例如,"""()""(())()""(()(()))" 都是有效的括号字符串。

如果有效字符串 S 非空,且不存在将其拆分为 S = A+B 的方法,我们称其为原语(primitive),其中AB 都是非空有效括号字符串。

给出一个非空有效字符串 S,考虑将其进行原语化分解,使得:S = P_1 + P_2 + ... + P_k,其中 P_i 是有效括号字符串原语。

S 进行原语化分解,删除分解中每个原语字符串的最外层括号,返回S

``` 示例 1: 输入:"(()())(())" 输出:"()()()" 解释: 输入字符串为 "(()())(())",原语化分解得到 "(()())" + "(())", 删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2: 输入:"(()())(())(()(()))" 输出:"()()()()(())" 解释: 输入字符串为 "(()())(())(()(()))",原语化分解得到 "(()())" + "(())" + "(()(()))", 删除每隔部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3: 输入:"()()" 输出:"" 解释: 输入字符串为 "()()",原语化分解得到 "()" + "()", 删除每个部分中的最外层括号后得到 "" + "" = ""。 ```

提示:

  • S.length <= 10000

  • S[i] 为 "(" 或 ")"

  • S 是一个有效括号字符串

2、解题思路

  • 设置一个栈,遇到"("入栈,遇到")"出栈,当栈为空,将中间字符假如结果中
class Solution:
    def removeOuterParentheses(self, S: str) -> str:
        stack = []
        res = ""
        pos = 0
        for index, i in enumerate(S):
            if i == "(":
                stack.append(i)
            else:
                stack.pop()

            if not stack:
                res += S[pos + 1:index]
                pos = index + 1
        return res