52-删除最外层的括号

自己的做法

算法思想

一个原语就表示一个不可再拆分的合法的括号序列。例如(())就是合法的，(()不合法。

()()也是合法的，但是它可拆分为()和()，所以不符合。

所以可以遍历序列，如果字符为(，就入栈；为)则出栈。

出栈后，如果栈为空，就代表该段序列是不可再拆分的合法的括号序列。

同时使用start来表示这段序列开始字符的索引。

然后将该段序列去掉最外层括号添加到res结果字符串末尾，同时start置为当前索引加1。

遍历结束，返回res。

算法思想

class Solution {
public:
    string removeOuterParentheses(string s) {
        if(s == "") {return s;}
        string res = "";
        stack<char> stack;
        int start = 0;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == ')') {
                stack.pop();
                if(stack.empty()) {
                    //start + 1，表示去掉外面括号的`(`,i - start - 1表示去掉外面括号的 ')'
                    res.append(s.substr(start + 1, i - start - 1));
                    start = i + 1;
                }
            } else {
                stack.push(s[i]);
            }
        }
        return res;
    }
};

性能分析

时间复杂度：$O(N)$。

空间复杂度：$O(N)$。

另一种做法

算法思想

一种优化的解法。

因为一个合法序列的(的数量和)的数量一定相同。

所以使用一个count遍历来计数，当遍历到的字符为(，则加1；为)，则减1。

当count为零时，代表找到了一段不可拆分的合法序列。

同样使用start变量表示这段序列的开始字符。

然后去掉该段字符的最外层括号添加到结果res字符串末尾。

算法实现

class Solution {
public:
    string removeOuterParentheses(string s) {
        if(s == "") {return s;}
        string res = "";
        int start = 0, count = 0;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == ')') {
                count--;
                if(count == 0) {
                    res.append(s.substr(start + 1, i - start - 1));
                    start = i + 1;
                }
            } else {
                count++;
            }
        }
        return res;
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(1)$。

无参考做法。