leetcode
leetcode 1101 ~ 1150
删除字符使字符串变好

删除字符使字符串变好

难度:

标签:

题目描述

代码结果

运行时间: 165 ms, 内存: 17.5 MB


/*
题目思路:
使用Java Stream API来实现去除连续三个相同字符的逻辑。我们可以用流来遍历字符串并过滤掉多余的字符。
可以使用collect操作收集最终结果。
*/

import java.util.stream.Collectors;

public class Solution {
    public String makeGoodString(String s) {
        StringBuilder result = new StringBuilder();
        int[] count = {1}; // 使用数组来模拟引用传递
        s.chars().mapToObj(c -> (char) c)
            .filter(c -> {
                if (result.length() == 0 || result.charAt(result.length() - 1) != c) {
                    count[0] = 1; // 重置计数器
                    return true;
                } else if (count[0] < 2) {
                    count[0]++;
                    return true;
                }
                return false;
            })
            .forEach(result::append);
        return result.toString();
    }
}

解释

方法:

该题解的主要思路是遍历字符串's',使用一个列表'li'来构建结果字符串。通过使用变量'cur'来记录当前正在处理的字符,以及'cnt'来计数当前字符连续出现的次数。如果当前字符与'cur'相同且'cnt'小于2,字符被添加到'li'中,并且'cnt'增加。如果当前字符不同于'cur',则更新'cur'和重置'cnt'为1,并将新字符添加到'li'中。这样就能保证构建的结果中任何字符的连续出现次数不会超过2,从而保证结果字符串是一个好字符串。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在实现中,如何处理输入字符串为空的情况?此时函数是否仍然能正确返回结果?
在给出的算法中,如果输入字符串为空,即`s`是一个空字符串,则循环不会执行,因为没有字符可遍历。由于列表`li`是空的,`"".join(li)`将返回一个空字符串。因此,即使输入为空,函数也能正确返回一个空字符串,符合预期结果。
🦆
题解中提到如果字符连续出现次数少于2则添加到结果列表中,但如何确保不会有三个连续字符被添加,特别是在边界转换(从一个字符转到另一个字符)时?
算法通过变量`cnt`来控制连续字符的添加。每次遇到新字符时,会重置`cnt`为1,并更新`cur`为当前字符,这样确保了每当字符变化时,计数器重新开始。若字符未改变且`cnt`已小于2,则`cnt`自增并添加字符。这样,即便是在字符边界转换时,由于`cnt`和`cur`的及时更新,可以保证任何字符连续出现的次数不会超过2次。
🦆
在处理连续字符时,为什么选择2作为连续出现次数的上限,而不是其他数字?
选择2作为连续出现次数的上限是基于题目要求,题目可能规定了最多允许连续出现同一字符两次来定义一个好字符串。这是基于题目的具体规则来设定的,若题目要求不同,连续出现次数的上限也会相应调整。
🦆
如果输入字符串中包含非常多的连续字符(如'a'重复数百次),算法处理效率如何,会有性能瓶颈吗?
该算法的时间复杂度为O(n),其中n是输入字符串的长度,因为每个字符只被遍历一次。空间复杂度也为O(n),因为在最坏的情况下(例如每两个字符就变化一次),结果字符串`li`可能接近原字符串长度。虽然算法在处理非常长的字符串时会占用较多内存,但整体上看,这是线性时间和空间复杂度,通常被认为是效率较高的。不过,如果`li`的长度成为问题或者内存有限制,可能需要考虑更优化的存储方法或在其他方面进行调整。

相关问题