Easy

题目描述

有效的括号字符串为空 “"、”(" + A + “)"、或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。

  • 例如，""、”()"、"(())()" 和 “(()(()))” 都是有效的括号字符串。

如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个有效括号字符串 s，考虑其原语化分解：s = P1 + P2 + … + Pk，其中 Pi 是有效括号字符串原语。

对 s 的每个原语化分解中的每个原语字符串，移除其最外层括号，返回 s 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解题思路

解题思路

这道题的关键是理解什么是原语括号字符串：一个有效的括号字符串，不能再拆分成两个非空的有效括号字符串。

我们需要识别每个原语字符串，然后去除它的最外层括号。

方法一：计数法（推荐）

使用一个计数器来跟踪括号的嵌套深度：

  • 遇到 '(' 时，计数器加1
  • 遇到 ')' 时，计数器减1
  • 当计数器为0时，表示找到了一个完整的原语

关键观察：对于每个原语，我们只需要跳过最外层的括号（第一个 '(' 和最后一个 ')'），保留内部的所有字符。

具体实现：

  • 维护一个深度计数器 depth
  • 当 depth > 1 时（表示不是最外层的左括号），将字符加入结果
  • 当 depth > 0 时遇到右括号（表示不是最外层的右括号），将字符加入结果

方法二：栈模拟

使用栈来模拟括号匹配过程，但实际上计数法更简洁高效。

时间复杂度：O(n)，只需要遍历字符串一次 空间复杂度：O(1)，只使用常数额外空间（不计输出字符串）

代码实现

class Solution {
public:
    string removeOuterParentheses(string s) {
        string result = "";
        int depth = 0;
        
        for (char c : s) {
            if (c == '(') {
                if (depth > 0) {
                    result += c;
                }
                depth++;
            } else {
                depth--;
                if (depth > 0) {
                    result += c;
                }
            }
        }
        
        return result;
    }
};

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

public class Solution {
    public string RemoveOuterParentheses(string s) {
        StringBuilder result = new StringBuilder();
        int depth = 0;
        
        foreach (char c in s) {
            if (c == '(') {
                if (depth > 0) {
                    result.Append(c);
                }
                depth++;
            } else {
                depth--;
                if (depth > 0) {
                    result.Append(c);
                }
            }
        }
        
        return result.ToString();
    }
}

/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function(s) {
    let result = '';
    let depth = 0;
    
    for (let char of s) {
        if (char === '(') {
            if (depth > 0) {
                result += char;
            }
            depth++;
        } else {
            depth--;
            if (depth > 0) {
                result += char;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型计数法
时间复杂度O(n)
空间复杂度O(1)

其中 n 是字符串 s 的长度。空间复杂度不包括输出结果占用的空间。