欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

栈中等 leetcode1249. 移除无效的括号

程序员文章站 2022-07-10 21:24:12
题目描述给你一个由 ‘(’、’)’ 和小写字母组成的字符串 s。你需要从字符串中删除最少数目的 ‘(’ 或者 ‘)’ (可以删除任意位置的括号),使得剩下的「括号字符串」有效。请返回任意一个合法字符串。有效「括号字符串」应当符合以下 任意一条 要求:空字符串或只包含小写字母的字符串可以被写作 AB(A 连接 B)的字符串,其中 A 和 B 都是有效「括号字符串」可以被写作 (A) 的字符串,其中 A 是一个有效的「括号字符串」题解class Solution { public St...

题目描述

给你一个由 ‘(’、’)’ 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 ‘(’ 或者 ‘)’ (可以删除任意位置的括号),使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。

有效「括号字符串」应当符合以下 任意一条 要求:

空字符串或只包含小写字母的字符串
可以被写作 AB(A 连接 B)的字符串,其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串,其中 A 是一个有效的「括号字符串」

题解

class Solution {
    public String minRemoveToMakeValid(String s) {
        int len = s.length();
        Stack<Integer> stack = new Stack();//存放左括号的坐标
        boolean[] sign = new boolean[len];//存放被踢除括号的坐标
        StringBuilder stringBuilder = new StringBuilder();//将剔除后的字符连接起来
        //寻找需要剔除的左右括号
        for(int i = 0;i < len;i++){
            int tmp = s.charAt(i);
            if(tmp == '('){
                stack.push(i);
            }
            if(tmp == ')'){
                if(stack.empty()){
                    sign[i] = true;
                }
                else{
                    stack.pop();
                }
            }
        }
        while(!stack.empty()){
            int i = stack.pop();
            sign[i] = true;
        }

        //遍历字符串,将需要保留的字符保存在stringBuilder中
        for(int i = 0;i < len;i++){
            if(sign[i] == true){
                continue;
            }
            stringBuilder.append(s.charAt(i));
        }
        String res = stringBuilder.toString();//stringBuilder转String
        return res;
    }
}

本文地址:https://blog.csdn.net/weixin_43260719/article/details/107347600