LeetCode题解-1021-删除最外层的括号

发表于 更新于 分类于

题目描述

有效括号字符串为空 (“”)、”(“ + A + “)” 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，””，”()”，”(())()” 和 “(()(()))” 都是有效的括号字符串。

如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：

S = P1 + P2 + … + Pk，其中 Pi 是有效括号字符串原语。

对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。

示例1:

输入：”(()())(())”

输出：”()()()”

解释：

输入字符串为 “(()())(())”，原语化分解得到 “(()())” + “(())”，

删除每个部分中的最外层括号后得到 “()()” + “()” = “()()()”。

示例2:

输入：”(()())(())(()(()))”

输出：”()()()()(())”

解释：

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

示例3:

输入：”()()”

输出：””

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

提示：

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

思路

这题想了一会，难度在于如何判断遍历到的这个字符是最外层的括号。其实只要记录之前左括号和右括号的个数，当遍历到的字符为右括号且此时之前的左括号个数比右括号个数大1，则表示碰到了最外层的括号。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public String removeOuterParentheses(String S) {
        Stack<Character> stack = new Stack<>();
        int leftCount = 0;
        int rightCount = 0;
        StringBuilder builder = new StringBuilder();
        for (Character c : S.toCharArray()) {
            if (leftCount == rightCount + 1 && c == ')') {
                // 这种情况表示遇到了最外层括号，则出栈
                Stack<Character> tmp = new Stack<>();
                while (stack.size() > 1) {
                    tmp.push(stack.pop());
                }
                while (!tmp.isEmpty()) {
                    builder.append(tmp.pop());
                }
                stack.pop();
                leftCount = 0;
                rightCount = 0;
            } else if (c == '(') {
                stack.push(c);
                leftCount++;
            } else if (c == ')') {
                stack.push(c);
                rightCount++;
            }
        }
        return builder.toString();
    }