专栏首页曌的晓痴LeetCode - 删除最外层的括号

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

提示:

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

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/remove-outermost-parentheses

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

这题的题目意思其实很简单,就是把一个有效的括号字符串,进行拆分,拆分成单独的几个有效括号字符串,然后去掉最外层的括号之后,再将其组装起来。

  1. 首先肯定是将这个入参S拆分成各个单独的有效括号字符串,这个步骤很简单,也就是遍历S中每个字符,然后判断左右括号,并计算括号数量,如果是左括号则计数器加1,右括号则减一;如果计数器达到0则认为到目前为止的字符串是一个有效的括号字符串,将其取出,接着遍历之后的字符
  2. 遍历列表中的每个有效括号字符串;分三种情况
    1. 字符串为空,则退出循环,不需要继续处理剩余的字符串了,且之前的操作也应该回退,所以这里使用了一个临时列表tmp用于表示当前处理的字符串
    2. 字符串长度为2,刚好是一对括号,将其设置为空字符串即可
    3. 长度大于2,且连续两个都是左括号,则将第一位和最后一位的括号都删掉即可
  3. 判断之前处理时是否存在长度为0的字符串,如果有则回退操作
  4. 遍历列表,将其所有的字符串都连接在一起后就是结果了

中文官网题解:

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();   
    }
}

结果:

运行效果还不错,这可能是最近算比较快的结果了。

本文分享自微信公众号 - 曌的晓痴(gh_543795945efe),作者:zxyAnkh

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode - 使括号有效的最少添加

    原题地址:https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/

    晓痴
  • LeetCode - 有效的括号

    LeetCode第20题,难度简单。因为有些是中文网做的,有些是之前英文网做的,所以有些题目虽然内容一样,但是题目序号是不一样的,我这里采用的是中文网的题目序号...

    晓痴
  • LeetCode - Z字形变换

    又双叒叕是三年前做的题目了,只有题目序号很大的,才是最近做的。因为最近做的都是些Easy模式的,用于找回感觉。

    晓痴
  • [牛客OI测试赛2]F假的数学游戏(斯特灵公式)

    $n! \approx \sqrt{2 \pi n} (\frac{n}{e})^n$

    attack
  • leetcode: 47. Permutations II

    JNingWei
  • [源码解析] Flink的Slot究竟是什么?(2)

    Flink的Slot概念大家应该都听说过,但是可能很多朋友还不甚了解其中细节,比如具体Slot究竟代表什么?在代码中如何实现?Slot在生成执行图、调度、分配资...

    罗西的思考
  • 【leetcode刷题】T175-判断子序列

    你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。

    木又AI帮
  • JavaScript之JS实现动画效果

        在前面的随笔中介绍了如何用DOM技术修改文档的央样式信息,用JavaScript添加样式信息可以节约我们的时间和精力,但总的来说,CSS仍是完成这类任务...

    郑小超.
  • 使用vcftools根据vcf文件计算种群核苷酸多样性

    找到了一份种群基因组学数据分析的教程,原文用的数据是2015年发表在science上的一篇论文Genomic islands of speciation sep...

    用户7010445
  • 创建自动滑雪模拟器

    关于自治代理,它们的应用和改进,有很多研究。所以在考虑自动驾驶汽车,它可以在没有任何碰撞的情况下在雪地上行驶。不幸的是,没有足够的资源和时间来构建一个真正的机器...

    代码医生工作室

扫码关注云+社区

领取腾讯云代金券