题目描述

[EN | CN]

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

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  1. S.length <= 10000
  2. S[i]"("")"
  3. S 是一个有效括号字符串。

解法 1:直接法

题目里说得有点绕,但是我们仔细分解题目要我们做什么,其实就是:

  1. 找到所有原语(即不能分解为 A + B 的有效括号字符串);
  2. 删除每个原语的最外层括号(即 ())。

第一个问题,我们怎么样 分解原语?其实很简单,就是顺序扫描,记录左括号 ( 跟右括号 ) 的数量,当两种括号的数量相等时,即到达了一个原语的终点。

第二个问题,怎么 删除每个原语的最外层括号?我们在刚开始、或者前一个原语刚结束的时候,遇到第一个左括号 (,就丢弃它(计数还是要加一);当我们继续遍历到该原语结束的时候(左右括号数量相等),最后一个右括号 ) 也丢弃掉。

假设字符串长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(n)$,保存结果。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def removeOuterParentheses(self, S: str) -> str:
        num_left, ret = 0, ''
        for i in S:
            if i == '(':
                num_left += 1
                if num_left > 1:
                    ret += '('
            else:
                num_left -= 1
                if num_left != 0:
                    ret += ')'
        return ret
  • 执行用时:32 ms,在所有 Python3 提交中击败了 99.77% 的用户。
  • 内存消耗:13.8 MB,在所有 Python3 提交中击败了 6.25% 的用户。