LeetCode 1021. 删除最外层的括号

迈不过友情╰ 2022-12-22 08:59 64阅读 0赞

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

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

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

利用栈，左右括号匹配时左括号出栈。左括号加入栈前如果栈不为空说明不是外层括号，右括号入栈后栈不为空说明不是外层括号：

class Solution { 
    public:
        string removeOuterParentheses(string S) { 
            string res;
            stack<char> cs;
    
            for (char c : S) { 
                if (c == '(') { 
                    if (cs.size()) {     // 左括号加入栈前栈不为空说明不是外层括号
                        res += c;
                    }
    
                    cs.push(c);
                } else if (c == ')') { 
                    if (cs.size() && cs.top() == '(') { 
                        cs.pop();
                    } else { 
                        cs.push(c);
                    }
    
                    if (cs.size()) {     // 右括号加入后栈不为空说明不是外层括号
                        res += c;
                    }
                }
            }
    
            return res;
        }
    };