2390. 从字符串中移除星号

🟠   🔖  栈 字符串 模拟  🔗 力扣 LeetCode

题目

You are given a string s, which contains stars *.

In one operation, you can:

• Choose a star in s.
• Remove the closest non-star character to its left , as well as remove the star itself.

Return the string afterall stars have been removed.

Note:

• The input will be generated such that the operation is always possible.
• It can be shown that the resulting string will always be unique.

Example 1:

Input: s = "leet**cod*e"

Output: "lecoe"

Explanation: Performing the removals from left to right:

• The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
• The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
• The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe".

There are no more stars, so we return "lecoe".

Example 2:

Input: s = "erase*****"

Output: ""

Explanation: The entire string is removed, so we return an empty string.

Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters and stars *.
• The operation above can be performed on s.

题目大意

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

在一步操作中，你可以：

• 选中 s 中的一个星号。
• 移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。

返回移除 所有 星号之后的字符串**。**

注意：

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

示例 1：

输入： s = "leet**cod*e"

输出： "lecoe"

解释： 从左到右执行移除操作：

• 距离第 1 个星号最近的字符是 "leet**cod*e" 中的 't' ，s 变为 "lee*cod*e" 。
• 距离第 2 个星号最近的字符是 "lee*cod*e" 中的 'e' ，s 变为 "lecod*e" 。
• 距离第 3 个星号最近的字符是 "lecod*e" 中的 'd' ，s 变为 "lecoe" 。

不存在其他星号，返回 "lecoe" 。

示例 2：

输入： s = "erase*****"

输出： ""

解释： 整个字符串都会被移除，所以返回空字符串。

提示：

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

解题思路

• 使用一个栈 stack 来存储字符。
• 遍历字符串 s，遇到普通字符时将其推入栈，遇到 * 时从栈中弹出一个字符。
• 最后将栈中的字符拼接成最终结果。

复杂度分析

• 时间复杂度：O(n)，因为只遍历了字符串一次。
• 空间复杂度：O(n)，因为在最坏情况下，栈中可能会存储所有字符（当没有 * 时）。

代码

/**
 * @param {string} s
 * @return {string}
 */
var removeStars = function (s) {
	let stack = [];
	for (let char of s) {
		if (char == '*') {
			stack.pop();
		} else {
			stack.push(char);
		}
	}
	return stack.join('');
};

相关题目

题号	标题	题解	标签	难度	力扣
844	比较含退格的字符串	[✓]	栈 双指针 字符串 1+	🟢	🀄️ 🔗
1047	删除字符串中的所有相邻重复项	[✓]	栈 字符串	🟢	🀄️ 🔗