简单

问题描述

有效括号字符串为空 ""、"(" + 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：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= s.length <= 105
• s[i] 为 '(' 或 ')'
• s 是一个有效括号字符串

栈

使用栈来记录括号的深度，遇到 '(' 入栈，遇到 ')' 出栈，我们需要删除的是最外层的括号，因此，当栈的深度大于 $1$ 时，遇到的括号都不是最外层的括号，我们都记录下来即可。

/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function (s) {
  let ans = ''
  const stack = []
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') stack.push(1)
    if (stack.length > 1) ans += s[i]
    if (s[i] === ')') stack.pop()
  }
  return ans
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

计数

可以看到，实际上栈的作用只是用于计数，跟栈里面的内容是没有任何关系的，因此我们可以使用一个变量对层级进行计数，无需开辟栈空间。

/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function (s) {
  let ans = ''
  let level = 0
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') level++
    if (level > 1) ans += s[i]
    if (s[i] === ')') level--
  }
  return ans
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$