『LeetCode』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：

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

示例 2：

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

示例 3：

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

提示：

\(1 <= s.length <= 10^{5}\)
\(s[i]\) 为 '(' 或 ')'
\(s\) 是一个有效括号字符串

题解

【删除最外层的括号】简单模拟

模拟

题目解释有点绕，但其实看标题删除最外层的括号应该大致能理解题意了，就是将括号字符串按最外层括号分段，然后每段都把最外层的括号去掉。

具体来说就是题目给出的字符串可以写成 \((A)(B)(C)\cdots\) 的形式，然后我们要将其变成 \(ABC\cdots\) 的形式 \(A, B, C\) 表示空串或合理的字符串。

PS: 对字符串创建操作，一般都有合适的构建函数，比直接进行字符串拼接快得多，例如 Python 的 str 的 join 方法, C++ 的 stringsteam, Java 的 StringBuilder.

# Code language: Python
class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        ans = list()
        cnt, start = 0, 0
        for idx, b in enumerate(s):
            if cnt == 0: # 这里一定是最外层的左括号
                start = idx + 1
            cnt += 1 if b == '(' else -1
            if cnt == 0: # 这里一定是最外层的右括号
                ans.append(s[start:idx])
        return "".join(ans)

// Code language: Java
class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0, n = s.length(), start = 0, cnt = 0; i < n; ++i) {
            if (cnt == 0)
                start = i + 1;
            cnt += s.charAt(i) == '(' ? 1 : -1;
            if (cnt == 0)
                sb.append(s.substring(start, i));
        }
        return sb.toString();
    }
}

// Code language: Cpp
class Solution {
public:
    string removeOuterParentheses(string s) {
        stringstream ss;
        for (int i = 0, n = s.length(), start = 0, cnt = 0; i < n; ++i) {
            if (cnt == 0)
                start = i + 1;
            cnt += s[i] == '(' ? 1 : -1;
            if (cnt == 0)
                ss << s.substr(start, i - start);
        }
        return ss.str();
    }
};

时间复杂度: \(O(n)\)
空间复杂度: \(O(n)\)

最后

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Github 查看更多题解