LEETCODE 1021. 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：

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

示例 2：

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

示例 3：

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

提示：

1. S.length <= 10000
2. S[i] 为 "(" 或 ")"
3. S 是一个有效括号字符串

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1021

解题思路分析：

这道题分为两步来思考，首先要找出所有的原语（primitive），然后再把原语的最外层删除。找到原语并不难，我们可以利用前缀和的思路来做，所有正括号看做是正1，反括号看做-1，然后从头开始相加，当和为0时，说明到当前位置为止正括号与反括号数量相同，这一段可以被看做是一个原语。然后再继续相加，直到出现下一个和为0的位置。举个例子说明：

String s = "(()())(())";

如果把正括号看做1，反括号看做-1的话，字符串s应该变为：

[(, (,  ), (,  ),  ), (, (,  ),  )] // 原始字符串
[1, 1, -1, 1, -1, -1, 1, 1, -1, -1] // 变换为1和-1之后

接下来我们计算一下前缀和，为了使用方便，我们在遇到正1时，采用count++（先赋值再加一），遇到-1时采用–count（先减一再赋值）来计算，这样能够保证相同层数深度的括号的前缀和是一致的，因此，前缀和应该为：

[1, 1, -1, 1, -1, -1, 1, 1, -1, -1] // 变换为1和-1之后
[0, 1,  1, 1,  1,  0, 0, 1,  1,  0] // 前缀和

这样我们能够很清楚看到，每一个数字都代表了当前括号的嵌套深度，嵌套深度大于0的部分即是答案。

看下实现代码：

public String removeOuterParentheses(String S) {
    StringBuilder res = new StringBuilder(); // 拼接返回结果使用
    int count=0; // 计算前缀和
    for(int i=0;i<S.length();i++){ // 循环字符串
        char c = S.charAt(i); // 取得当前字符
        if(c=='('){ // 如果为正括号
            if(count++>0){ // 如果前缀和大于0则加入到res中（注意是count++）
                res.append(c);
            }
        }else{
            if(--count>0){ // 如果前缀和大于0则加入到res中（注意是--count）
                res.append(c);
            }
        }
    }
    return res.toString();
}

本题有个需要注意的地方，在拼接字符串时不要直接使用加号，利用StringBuilder可极大的提高运行速度。

本解法运行时间为3ms。

Runtime: 3 ms, faster than 69.07% of Java online submissions for Remove Outermost Parentheses.

Memory Usage: 37.7 MB, less than 18.18% of Java online submissions for Remove Outermost Parentheses.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1021-remove-outermost-parentheses-解题思路分析/