2390. 从字符串中移除星号

1.题目

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

在一步操作中，你可以：

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

注意：

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

示例 1：

输入：s = "leet*code"
输出："lecoe"
解释：从左到右执行移除操作：

• 距离第 1 个星号最近的字符是 "leetcode" 中的 't' ，s 变为 "leecod*e" 。
• 距离第 2 个星号最近的字符是 "leecode" 中的 'e' ，s 变为 "lecod*e" 。
• 距离第 3 个星号最近的字符是 "lecod*e" 中的 'd' ，s 变为 "lecoe" 。
  不存在其他星号，返回 "lecoe" 。
  示例 2：

输入：s = "erase*****"
输出：""
解释：整个字符串都会被移除，所以返回空字符串。

提示：

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

2.思路

• 方法：栈：先进后出

  • 基本思想：
    1.首先定义了一个 Stack 类，并使用泛型来指定栈中元素的类型。然后，我们使用一个私有变量 elements 来保存栈中的元素。接着，我们定义了 push、pop、top 和 isEmpty 四个方法来实现栈的基本功能。
    2.push 方法用于向栈中添加元素，我们可以使用 List 的 :: 操作符将新元素添加到 List 的头部。
    3.pop 方法用于弹出栈顶元素，我们使用模式匹配来处理空栈和非空栈的情况。如果栈为空，则返回 None，否则弹出 List 的头部元素，并将剩余元素赋值给 elements。
    4.top 方法用于获取栈顶元素，如果 为空，则返回 None。

isEmpty 方法用于判断栈是否为空，我们使用 List 的 isEmpty 方法来判断。

3.代码

object Solution {
  def removeStars(s: String): String = {
    import scala.collection.mutable._
    val charArray: Array[Char] = s.toCharArray
    val stringBuilder = new StringBuilder
    val stack = new Stack[Char]
    for(ch<-charArray){
      if(ch=='*')  stack.pop()
      else stack.push(ch)
    }
    // 栈是先进后出，所以倒序进行拼接
    for(i<- stack.length-1 to 0 by -1){
      stringBuilder.append(stack(i))
    }
    return stringBuilder.toString()
  }
}

4.复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)