【数据结构和算法】从字符串中移除星号

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集

---

文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1 用 stringBuilder 模拟栈

2.2 传统栈实现

三、代码

3.1 用 stringBuilder 模拟栈

3.2 传统栈实现

四、复杂度分析

4.1 用 stringBuilder 模拟栈

4.2 传统栈实现

---

前言

这是力扣的 2390 题，难度为中等，解题方案有很多种，本文讲解我认为最奇妙的一种。

慢慢开始栈的模块了，这道题是一道非常好的栈的例题，很有代表性。

---

一、题目描述

给你一个包含若干星号?*?的字符串?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 <= 105
• s?由小写英文字母和星号?*?组成
• s?可以执行上述操作

---

二、题解

2.1 用 stringBuilder 模拟栈

思路与算法：

这道题要求返回字符串 sss 移除所有星号之后的字符串。可以模拟生成字符串的过程得到移除所有星号之后的字符串。对于每个输入字符，执行如下操作。

• 如果输入字符不是星号，则将输入字符拼接到字符串的末尾。
• 如果输入字符是星号，则移除字符串的末尾字符。由于给定的字符串保证总是可以执行移除操作，因此不需要判断字符串是否为空。

由于每次遇到星号时移除字符串的末尾字符，符合后进先出的规则，因此可以使用栈模拟字符串的输入，栈底对应字符串的首端，栈顶对应字符串的末尾。

实现方面，可以使用可变字符串模拟栈，遍历结束之后，可变字符串的内容即为结果字符串。

2.2 传统栈实现

思路与算法：

读题可知，题目要求我们对串进行删除'*'元素操作。

注意题目对删除要求的说法：“移除星号左侧最近的那个非星号字符，并移除该星号自身。”

一说到左侧最近这几个字眼就要眼睛放光了，所谓删除左侧，也就说要删除上一次遍历操作的元素，也就是说这个操作是和时间顺序有联系的，回想起我们曾经学过数据结构，有哪种结构是对元素操作的先后顺序密切相关的呢？

相信你一定就能快速思索出来答案：队列 和 栈。

• 队列，先进先出，对最旧的那批元素先进行操作。
• 栈，后进先出，对最新的那批元素先进进行操作。

显然，要删除离'*'最近的元素肯定是用栈最好，因为要遍历到'*'号时，要删除的左侧元素就我们上次循环遍历过的。

---

三、代码

3.1 用 stringBuilder 模拟栈

Java版本：

class Solution {
    public String removeStars(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)=='*'){
                sb.deleteCharAt(sb.length()-1);
            }else{
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

C++版本：?

class Solution {
public:
    string removeStars(string s) {
        //创建一个答案串
        string ans;
        for(auto c : s){
            if(c != '*'){
                ans.push_back(c);
            }else{
                ans.pop_back();
            }
        }
        return ans;
    }
};

3.2 传统栈实现

Java版本：

class Solution {
    public String removeStars(String s) {
        ArrayDeque<Character> deque = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '*') {
                deque.pollLast();
            } else {
                deque.add(s.charAt(i));
            }
        }
        StringBuilder sb = new StringBuilder();
        for (Character c : deque) {
            sb.append(c);
        }
        return sb.toString();
    }
}

C++版本：

class Solution {
public:
    string removeStars(string s) {
        std::stack<char> stack;
        for (auto c : s) {
            if (stack.empty()) {
                stack.push(c);
                continue;
            }
            if (c == '*') {
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        string res;
        while (!stack.empty()) {
            res += stack.top();
            stack.pop();
        }
        std::reverse(res.begin(), res.end());
        return res;
    }
};

Python版本：

class Solution:
    def removeStars(self, s: str) -> str:
        st = []
        for c in s:
            if c == '*': st.pop()
            else: st.append(c)
        return ''.join(st)

Go版本：

func removeStars(s string) string {
	st := []rune{}
	for _, c := range s {
		if c == '*' {
			st = st[:len(st)-1]
		} else {
			st = append(st, c)
		}
	}
	return string(st)
}

---

四、复杂度分析

4.1 用 stringBuilder 模拟栈

• 时间复杂度：O(n)，其中?n?为?s?的长度。
• 空间复杂度：O(n)。

4.2 传统栈实现

• 时间复杂度：O(n)，其中?n?为?s?的长度。
• 空间复杂度：O(n)。

---