LeetCode - 删除最外层的括号
LeetCode第1021题，难度简单。不过这题题目很长，代码也很长。
原题地址：https://leetcode-cn.com/problems/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：
输入："()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。提示：
- S.length <= 10000
- S[i] 为 "(" 或 ")"
- S 是一个有效括号字符串
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-outermost-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
这题的题目意思其实很简单，就是把一个有效的括号字符串，进行拆分，拆分成单独的几个有效括号字符串，然后去掉最外层的括号之后，再将其组装起来。
- 首先肯定是将这个入参S拆分成各个单独的有效括号字符串，这个步骤很简单，也就是遍历S中每个字符，然后判断左右括号，并计算括号数量，如果是左括号则计数器加1，右括号则减一；如果计数器达到0则认为到目前为止的字符串是一个有效的括号字符串，将其取出，接着遍历之后的字符
- 遍历列表中的每个有效括号字符串；分三种情况
- 字符串为空，则退出循环，不需要继续处理剩余的字符串了，且之前的操作也应该回退，所以这里使用了一个临时列表tmp用于表示当前处理的字符串
- 字符串长度为2，刚好是一对括号，将其设置为空字符串即可
- 长度大于2，且连续两个都是左括号，则将第一位和最后一位的括号都删掉即可
- 判断之前处理时是否存在长度为0的字符串，如果有则回退操作
- 遍历列表，将其所有的字符串都连接在一起后就是结果了
中文官网题解：
https://leetcode-cn.com/problems/remove-outermost-parentheses/solution/
个人题解：
class Solution {
public String removeOuterParentheses(String S) {
if (S.length() == 0) {
return "";
}
int lastIndex = -1;
int count = 0;
List<String> list = new ArrayList<>();
char[] chars = S.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(') {
count++;
} else {
count--;
}
if (count == 0) {
list.add(S.substring(lastIndex + 1, i + 1));
lastIndex = i;
}
}
boolean flag = false;
List<String> tmp = new ArrayList<>(list);
for (int i = 0; i < tmp.size(); i++) {
String s = tmp.get(i);
if (s.length() == 0) {
flag = true;
break;
} else if (s.length() == 2) {
tmp.set(i, "");
} else if (s.charAt(0) == '(' && s.charAt(1) == '(') {
tmp.set(i, s.substring(1, s.length() - 1));
}
}
if (!flag) {
list = tmp;
}
StringBuilder stringBuilder = new StringBuilder();
for (String s : list) {
stringBuilder.append(s);
}
return stringBuilder.toString();
}
}结果：
运行效果还不错，这可能是最近算比较快的结果了。
