1021. 删除最外层的括号

题目大意
解题方法
- 栈
  - 代码
  - 复杂度
- 记数
  - 代码
  - 复杂度
总结

大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

今天的题目需要我这个语文课代表进行翻译。

题目中给出的字符串是由小括号"(",")"构成的。什么是有效的括号字符串呢？

空字符串 ""
左右完全匹配的括号，如 "()"，"(())"，"(()())"。

哪些不是有效的括号字符串呢？

左右括号数不等的，如 "("，"(()"，"(((()"
左右顺序错了的，如 ")("，"))("

题目中所谓的「原语」就是不能再拆分成两个有效括号字符串 A + B的。

所有的「原语」，它的整体就是一个完整的括号匹配字符串，无法再一刀两断了。
而「非原语」，把它从某个部分切开以后，可以变成两个完全匹配的括号字符串。

举个例子：

"()","(())", "(()())" 是「原语」，不能再拆分了。
"()()", "(())()"不是「原语」，因为可以再拆分。

题目让我们找出所有的「原语」，然后把每个「原语」的最外边一层 "("、")"去掉

解题方法

栈

题目扯了半天，就是让我们实现一个括号匹配算法。

谈到括号匹配算法，就会想到「栈」。

本题的做法不难，核心就是：当栈为空的时候，说明已经形成了『原语』。

从左向右遍历字符串
当遇到 "("时，将其入栈；
当遇到 ")"时，说明匹配了前面最近一个 "("，因此将栈顶弹出；

而结果字符串 res，需要根据当前的 "(" 或者 ")"是不是「原语」的开头和结束来决定。

当"("入栈前，栈是空，说明 "(" 是『原语』的开头，因此不放入 res中。
当遇到 ")" 弹出栈顶以后，栈是空，说明 ")" 是『原语』的结束，因此不放入 res中。

具体过程如下面的动画所示。

代码

判断"(" 或者 ")"是不是「原语」的开头和结束，还是挺巧妙的。因此需要注意 $3$ 个 1021. 删除最外层的括号 - 图2 的位置。

class Solution {
public:
    string removeOuterParentheses(string s) {
        stack<char> st;
        string res;
        for (char c : s) {
            if (c == ')')
                st.pop();
            if (!st.empty())
                res += c;
            if (c == '(') {
                st.push('(');
            }
        }
        return res;
    }
};

复杂度

时间复杂度：，是字符串长度。
空间复杂度：。

记数

我们也发现，题目给出的 s 是一个有效括号字符串。

我们可以使用一个变量 1021. 删除最外层的括号 - 图6 统计「"("比 ")"多的个数」，当 1021. 删除最外层的括号 - 图7 时，说明左右括号完成了匹配，形成了「原语」。

代码

class Solution {
public:
    string removeOuterParentheses(string s) {
        int count = 0;
        string res;
        for (char c : s) {
            if (c == ')') {
                count --;
            }
            if (count != 0) {
                res += c;
            }
            if (c == '(') {
                count ++;
            }
        }
        return res;
    }
};