1021.删除最外层的括号：一次遍历

【LetMeFly】1021.删除最外层的括号：一次遍历

力扣题目链接：https://leetcode.cn/problems/remove-outermost-parentheses/

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

题目大意

题目大概意思就是要把原字符串拆分成(...)(...)(...)的样子。

例如某个字符串可以拆分成(a)(b)(c)(d)，那么就返回abcd。

其中，我们把(a)、(b)、(c)、(d)记为原语。

也就是说要把由原语组成的字符串拆分成每个原语，然后把每个原语去掉两边的括号并按顺序拼接后返回。

解题思路

用变量$left$来记录未配对的左括号的数量。

从左到右遍历字符串，遇到左括号$left$就$+1$，遇到右括号就$-1$。

也就是用计数来模拟栈。

具体方法：模拟

遇到左括号，如果计数之前$left$为$0$，那么就说明这是一个原语的*开始。原语的最左*括号是不用作为答案返回的，因此只有当$left$不为$0$的时候才返回当前字符。

遇到右括号，如果计数之后$left$为$0$，那么就说明这是一个原语的结束。原语的最右括号是不用作为答案返回的，因此只有当$left$不为$0$的时候才返回当前字符。

时空复杂度

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

AC代码

C++

/*
 * @LastEditTime: 2022-05-28 10:36:45
 */
// 原语（primitive）
class Solution {
public:
    string removeOuterParentheses(string s) {
        string ans;
        int left = 0;  // 当前有几个未配对的左括号
        for (char& c : s) {
            if (c == '(') {
                if (left) {
                    ans += '(';
                }
                left++;
            }
            else {
                left--;
                if (left) {
                    ans += ')';
                }
            }
        }
        return ans;
    }
};

C++ - 写法二

/*
 * @LastEditTime: 2026-10-08 08:58:16
 */
#define IFSKIP if (!layer) skip = true

class Solution {
public:
    string removeOuterParentheses(const string& s) {
        string ans;
        for (int i = 0, n = s.size(), layer = 0; i < n; i++) {
            bool skip = false;
            if (s[i] == '(') {
                IFSKIP;
                layer++;
            } else {
                layer--;
                IFSKIP;
            }

            if (!skip) {
                ans.push_back(s[i]);
            }
        }
        return ans;
    }
};

Python

'''
LastEditTime: 2026-10-08 09:26:04
'''
class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        ans = []
        layer = 0
        for c in s:
            if c == '(':
                if layer:
                    ans.append(c)
                layer += 1
            else:
                layer -= 1
                if layer:
                    ans.append(c)
        return ''.join(ans)
                

Java

/*
 * @LastEditTime: 2026-10-08 09:24:07
 */
class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder ans = new StringBuilder();
        for (int i = 0, n = s.length(), layer = 0; i < n; i++) {
            boolean skip = false;
            if (s.charAt(i) == '(') {
                if (layer++ == 0) {
                    skip = true;
                }
            } else {
                if (--layer == 0) {
                    skip = true;
                }
            }
            if (!skip) {
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }
}

Go

/*
 * @LastEditTime: 2026-10-08 09:15:54
 */
package main

import "strings"

func removeOuterParentheses(s string) string {
    var ans strings.Builder
    layer := 0
    for _, c := range s {
        skip := false
        if c == '(' {
            if layer == 0 {
                skip = true
            }
            layer++
        } else {
            layer--
            if layer == 0 {
                skip = true
            }
        }
        if !skip {
            ans.WriteRune(c)
        }
    }
    return ans.String()
}

Rust

/*
 * @LastEditTime: 2026-10-08 09:32:53
 */
impl Solution {
    pub fn remove_outer_parentheses(s: String) -> String {
        let mut ans = String::new();
        let mut layer = 0;
        for c in s.bytes() {
            if c == b'(' {
                if layer != 0 {
                    ans.push(c as char);
                }
                layer += 1;
            } else {
                layer -= 1;
                if layer != 0 {
                    ans.push(c as char);
                }
            }
        }
        ans
    }
}

End

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源