题目大意：
删除最外层的括号
有效括号字符串为空 (“”)、”(” + 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：
输入：”()()”
输出：””
解释：
输入字符串为 “()()”，原语化分解得到 “()” + “()”，
删除每个部分中的最外层括号后得到 “” + “” = “”。
提示：
S.length <= 10000S[i]为"("或")"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-解题思路分析/
View Comments (0)