题目
概述：给定一组并列的且正确匹配的括号，让你消去每组并列括号的最外层括号
输入：一组并列的且正确匹配的括号字符串, 长度范围[0, 10000]
输入子项："("或")"
输出：去掉最外层括号的字符串
出处：https://leetcode-cn.com/problems/remove-outermost-parentheses/
思路
括号问题使用栈解决
-
将字符串中的字符依次入栈：
- 当前字符为"(" => 直接入栈
- 当前字符为")"：
- 栈中元素个数 > 1 => 栈顶元素出栈
- 栈中元素个数 == 1 => 栈顶元素出栈，标记这两个括号是最外层括号
将原字符串中被标记为最外层括号的字符全部删除
代码
class Solution {
public String removeOuterParentheses(String S) {
if (S == null || S.length() == 0) {
return "";
}
LinkedList<Integer> stack = new LinkedList<>();
boolean[] remains = new boolean[S.length()];
int top;
StringBuilder result = new StringBuilder();
Arrays.fill(remains, true);
stack.push(0);
remains[0] = false;
for (int i = 1; i < S.length(); ++i) {
switch (S.charAt(i)) {
case '(':
stack.push(i);
break;
case ')':
top = stack.pop();
if (stack.size() == 0) {
remains[i] = false;
remains[top] = false;
}
break;
}
}
for (int i = 0; i < S.length(); ++i) {
if (remains[i]) {
result.append(S.charAt(i));
}
}
return result.toString();
}
}
