Question

1021. 删除最外层的括号

English Version

题目描述

有效括号字符串为空 ""、"(" + 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$ 时，说明当前括号不是最外层括号，将其加入结果字符串。遇到右括号 ')' 计数器减一，此时计数器不为 $0$ 时，说明当前括号不是最外层括号，将其加入结果字符串。

时间复杂度 $O(n)$，其中 $n$ 为字符串长度。忽略答案字符串的空间开销，空间复杂度 $O(1)$。

class Solution:
  def removeOuterParentheses(self, s: str) -> str:
    ans = []
    cnt = 0
    for c in s:
      if c == '(':
        cnt += 1
        if cnt > 1:
          ans.append(c)
      else:
        cnt -= 1
        if cnt > 0:
          ans.append(c)
    return ''.join(ans)

class Solution {
  public String removeOuterParentheses(String s) {
    StringBuilder ans = new StringBuilder();
    int cnt = 0;
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      if (c == '(') {
        if (++cnt > 1) {
          ans.append(c);
        }
      } else {
        if (--cnt > 0) {
          ans.append(c);
        }
      }
    }
    return ans.toString();
  }
}

class Solution {
public:
  string removeOuterParentheses(string s) {
    string ans;
    int cnt = 0;
    for (char& c : s) {
      if (c == '(') {
        if (++cnt > 1) {
          ans.push_back(c);
        }
      } else {
        if (--cnt) {
          ans.push_back(c);
        }
      }
    }
    return ans;
  }
};

func removeOuterParentheses(s string) string {
  ans := []rune{}
  cnt := 0
  for _, c := range s {
    if c == '(' {
      cnt++
      if cnt > 1 {
        ans = append(ans, c)
      }
    } else {
      cnt--
      if cnt > 0 {
        ans = append(ans, c)
      }
    }
  }
  return string(ans)
}

function removeOuterParentheses(s: string): string {
  let res = '';
  let depth = 0;
  for (const c of s) {
    if (c === '(') {
      depth++;
    }
    if (depth !== 1) {
      res += c;
    }
    if (c === ')') {
      depth--;
    }
  }
  return res;
}

impl Solution {
  pub fn remove_outer_parentheses(s: String) -> String {
    let mut res = String::new();
    let mut depth = 0;
    for c in s.chars() {
      if c == '(' {
        depth += 1;
      }
      if depth != 1 {
        res.push(c);
      }
      if c == ')' {
        depth -= 1;
      }
    }
    res
  }
}

方法二

class Solution:
  def removeOuterParentheses(self, s: str) -> str:
    ans = []
    cnt = 0
    for c in s:
      if c == '(':
        cnt += 1
      if cnt > 1:
        ans.append(c)
      if c == ')':
        cnt -= 1
    return ''.join(ans)

class Solution {
  public String removeOuterParentheses(String s) {
    StringBuilder ans = new StringBuilder();
    int cnt = 0;
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      if (c == '(') {
        ++cnt;
      }
      if (cnt > 1) {
        ans.append(c);
      }
      if (c == ')') {
        --cnt;
      }
    }
    return ans.toString();
  }
}

class Solution {
public:
  string removeOuterParentheses(string s) {
    string ans;
    int cnt = 0;
    for (char& c : s) {
      if (c == '(') {
        ++cnt;
      }
      if (cnt > 1) {
        ans.push_back(c);
      }
      if (c == ')') {
        --cnt;
      }
    }
    return ans;
  }
};

func removeOuterParentheses(s string) string {
  ans := []rune{}
  cnt := 0
  for _, c := range s {
    if c == '(' {
      cnt++
    }
    if cnt > 1 {
      ans = append(ans, c)
    }
    if c == ')' {
      cnt--
    }
  }
  return string(ans)
}