您的位置:首页 > 科技 > IT业 > LeetCode:2390. 从字符串移除*号 使用栈,时间复杂度O(N)

LeetCode:2390. 从字符串移除*号 使用栈,时间复杂度O(N)

2024/11/4 1:23:03 来源:https://blog.csdn.net/weixin_60214397/article/details/142265978  浏览:    关键词:LeetCode:2390. 从字符串移除*号 使用栈,时间复杂度O(N)

2390. 从字符串移除*号

today 2390. 从字符中移除*号

题目表述

给你一个包含若干星号 * 的字符串 s

在一步操作中,你可以:

选中 s 中的一个星号。
移除星号 左侧 最近的那个 非星号 字符,并移除该星号自身。
返回移除 所有 星号之后的字符串。

注意:

  • 生成的输入保证总是可以执行题面中描述的操作。
  • 可以证明结果字符串是唯一的。

示例1:

输入: s = “leet**cod*e”
输出: “lecoe”
解释: 从左到右执行移除操作:

  • 距离第 1 个星号最近的字符是 “leet**code" 中的 ‘t’ ,s 变为 "leecod*e” 。
  • 距离第 2 个星号最近的字符是 “leecode” 中的 ‘e’ ,s 变为 “lecod*e” 。
  • 距离第 3 个星号最近的字符是 “lecod*e” 中的 ‘d’ ,s 变为 “lecoe” 。
    不存在其他星号,返回 “lecoe” 。

示例2:

输入: s = “erase*****”
输出: “”
解释:整个字符串都会被移除,所以返回空字符串。

提示:

  • 1 <= s.length <= 10^5
  • s由小写英文字母和星号*组成
  • s 可以执行上述操作

题目解析

题目要求我们从字符串 s 中移除所有星号,并返回移除星号之后的字符串。

我们可以使用栈来解决这个问题。通过维护一个栈来存储最终结果res,初始时栈为空。我们从前到后遍历字符串 s:

  • 如果遇到星号,我们将栈中的栈顶元素弹出。
  • 如果遇到非星号,我们将其压入栈中。
  • 遍历完成后,栈中的元素即为最终结果。

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n),遍历字符串 s 一次。
  • 空间复杂度: O ( n ) O(n) O(n),栈最多存储 n 个元素。

代码实现

Python实现:

class Solution(object):def removeStars(self, s):stack = []for char in s:if char == '*':stack.pop()  # 移除栈顶元素,即上一个添加的字符else:stack.append(char)  # 将非 '*' 字符压入栈中return ''.join(stack)  # 最后将栈中的字符连接成字符串返回

C++实现:

class Solution {
public:string removeStars(string s) {string res;for (char c : s) {if (c == '*') {res.pop_back();  // 遇到 '*' 时移除最后一个字符} else {res.push_back(c);  // 添加非 '*' 的字符}}return res;}
};

Go实现:

func removeStars(s string) string {// 预先分配切片容量,避免多次动态扩容res := make([]byte, 0, len(s)) for i := 0; i < len(s); i++ {if s[i] == '*' {res = res[:len(res)-1]  // 从切片中移除最后一个元素} else {res = append(res, s[i])  // 非 '*' 字符加入切片}}return string(res)  // 将最终的 byte 切片转化为字符串
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com