leetcode
leetcode 2051 ~ 2100
从字符串中移除星号

从字符串中移除星号

难度:

标签:

题目描述

代码结果

运行时间: 104 ms, 内存: 17.2 MB


/*
 * 题目思路:
 * 给定一个字符串s,其中包含若干星号*。
 * 在一步操作中,我们可以选中s中的一个星号,并移除星号左侧最近的那个非星号字符,同时移除该星号自身。
 * 返回移除所有星号之后的字符串。
 * 我们可以使用Java Stream来实现这个功能。通过遍历字符串并使用一个栈来存储非星号字符,遇到星号时弹出栈顶元素,最后将栈中元素组合成字符串。
 */

import java.util.Stack;
import java.util.stream.Collectors;

public class SolutionStream {
    public String removeStars(String s) {
        Stack<Character> stack = new Stack<>();
        s.chars().forEach(c -> {
            if (c == '*') {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                stack.push((char) c);
            }
        });
        return stack.stream().map(String::valueOf).collect(Collectors.joining());
    }
}

解释

方法:

此题解使用了一个栈(列表res)的结构来实现字符的暂存和删除操作。遍历字符串s中的每个字符:当遇到星号'*'时,从栈顶弹出一个元素,即删除星号左侧的非星号字符;当遇到非星号字符时,将其推入栈中。这样,栈中最终保存的就是所有未被星号删除的字符。最后,使用''.join()方法将栈中的字符合并成一个字符串作为最终结果。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在实现中,为什么选择使用栈作为数据结构来解决这个问题?
栈是一种后进先出(LIFO)的数据结构,非常适合处理与最近相关的操作。在这个问题中,每当遇到星号`*`时,我们需要删除其左侧最近的一个非星号字符。栈可以让我们方便地访问到最后插入的元素,并在遇到星号时迅速移除它,从而有效地处理字符的添加与删除,保证时间复杂度为线性O(n)。
🦆
如果字符串`s`以一个星号`*`开始,这种情况下的行为是如何处理的?
在题解中未明确检查栈是否为空就直接使用`res.pop()`。理论上,如果`s`以星号`*`开始,这将尝试从一个空栈中弹出元素,导致运行时错误。因此在实际实现中,应当添加一个检查以确保栈不为空再执行`pop`操作,避免错误。
🦆
为什么在遇到星号时,可以直接使用`res.pop()`而不检查栈是否为空?
在题解的原始实现中,确实没有检查栈是否为空就直接执行了`res.pop()`。这种做法默认字符串中的星号数量不会超过非星号字符的数量,是基于题目背景或已知的输入约束。然而,为了代码的健壮性,最好在执行`pop`前检查栈是否为空,以避免因弹出空栈而导致错误。
🦆
这种方法中,是否有可能出现对栈的操作次数超过字符串长度的情况?
在这种方法中,每个字符最多被处理两次——一次是被推入栈中,另一次可能是从栈中弹出。因此,总的操作次数(包括`push`和`pop`)最多是字符串长度的两倍,不会超过字符串长度。整体的时间复杂度维持在O(n)。

相关问题