侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【栈, 计数】删除最外层的括号

GabrielxD
2022-05-28 / 0 评论 / 0 点赞 / 465 阅读 / 916 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1021. 删除最外层的括号


有效括号字符串为空 """(" + A + ")"A + B ,其中 AB 都是有效的括号字符串,+ 代表字符串的连接。

  • 例如,"""()""(())()""(()(()))" 都是有效的括号字符串。

如果有效字符串 s 非空,且不存在将其拆分为 s = A + B 的方法,我们称其为原语(primitive),其中 AB 都是非空有效括号字符串。

给出一个非空有效字符串 s,考虑将其进行原语化分解,使得:s = P_1 + P_2 + ... + P_k,其中 P_i 是有效括号字符串原语。

s 进行原语化分解,删除分解中每个原语字符串的最外层括号,返回 s

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 1 <= s.length <= 10^5
  • s[i]'('')'
  • s 是一个有效括号字符串

解题

方法一:栈

思路

遍历 s,并用一个栈(stack)来表示括号的深度。遇到 '(' 则将字符入栈,遇到 ')' 则将栈顶字符出栈。栈从空到下一次空的过程,则是扫描了一个原语的过程。一个原语中,首字符和尾字符应该舍去,其他字符需放入结果字符串中。因此:

  • 在遇到 '(' 并将字符入栈后,如果栈的深度为 1,则不把字符放入结果;
  • 在遇到 ')' 并将栈顶字符出栈后,如果栈为空,则不把字符放入结果。
  • 其他情况下,需要把字符放入结果。

代码

class Solution {
    public String removeOuterParentheses(String s) {
        Deque<Character> stack = new LinkedList<>();
        StringBuilder ans = new StringBuilder();
        for (char curr : s.toCharArray()) {
            switch (curr) {
                case '(':
                    stack.push('curr');
                    if (stack.size() > 1) ans.append(curr);
                    break;
                case ')':
                    stack.pop();
                    if (stack.size() > 0) ans.append(curr);
                    break;
            }
        }
        return ans.toString();
    }
}

简化判断

class Solution {
    public String removeOuterParentheses(String s) {
        Deque<Character> stack = new LinkedList<>();
        StringBuilder ans = new StringBuilder();
        for (char curr : s.toCharArray()) {
            if (curr == ')') stack.pop();
            if (!stack.isEmpty()) ans.append(curr);
            if (curr == '(') stack.push(curr);
        }
        return ans.toString();
    }
}

优化

由上面代码可以看出,我们只关心栈的深度,不关心栈里有什么,只需要维护栈深度(depth)即可。

class Solution {
    public String removeOuterParentheses(String s) {
        int depth = 0;
        StringBuilder ans = new StringBuilder();
        for (char curr : s.toCharArray()) {
            if (curr == ')') depth--;
            if (depth > 0) ans.append(curr);
            if (curr == '(') depth++;
        }
        return ans.toString();
    }
}

另一种理解:计数

思路

初始化计数器(count),遍历字符串 s

  • 遇到左括号 '(' 则将 count 加上 1
  • 遇到右括号 ')' 则将 count 减去 1

找规律:

image-20220528014306421

代码

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder ans = new StringBuilder();
        int count = 0;
        for (char curr : s.toCharArray()) {
            switch (curr) {
                case '(':
                    count++;
                    if (count > 1) ans.append(curr);
                    break;
                case ')':
                    count--;
                    if (count > 0) ans.append(curr);
                    break;
            }
        }
        return ans.toString();
    }
}
0

评论区