🍥

Hang Zhang

genius.

Data Structure and Algorithm

Removing Stars from a String

2390. 从字符串中移除星号

分析

利用栈的性质：
- 遍历字符串 s，将每个字符逐个处理
- 如果遇到非星号字符，将其加入结果字符串 res 中（模拟入栈操作）
- 如果遇到星号 *，移除结果字符串 res 的最后一个字符（模拟出栈操作）
最终结果：
- 遍历完成后，结果字符串 res 即为移除所有星号及其左侧字符后的字符串

时间复杂度

每个字符只被处理一次

总时间复杂度 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution
             {
public:
    string removeStars(string s)
    {
        std::string res; // 用作结果栈
        for (auto c : s)
        {
            if (c == '*')
                res.pop_back(); // 移除最后一个字符
            else
                res.push_back(c); // 添加当前字符
        }
        return res;
    }
};