从字符串中移除星号 图解题解
这道题到底在问什么
- 输入
- s = "leet**cod*e"
- 输出
- "lecoe"
- 输入
- s = "erase*****"
- 输出
- "" (空串)
- 输入
- s = "abc"
- 输出
- "abc" (无星号原样返回)
最优解：一步一步想明白
- 3为什么栈天然对路?因为栈顶永远是「最后一个还留着的字符」,而 * 要删的恰恰就是它。入栈 = 留下,弹栈 = 被星号删掉。
- 4开始前栈是空的。指针会从第 0 位一路扫到末尾,边走边维护这个栈。栈里此刻没有任何字符。
- 5扫到第 0 位是普通字母 "l"。它不是星号,先暂时留下来,把它压进栈里。
- 6"l" 入栈,成为新的栈顶。栈从底到顶现在是 [l]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
- 7扫到第 1 位是普通字母 "e"。它不是星号,先暂时留下来,把它压进栈里。
- 8"e" 入栈,成为新的栈顶。栈从底到顶现在是 [l e]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
- 9扫到第 2 位是普通字母 "e"。它不是星号,先暂时留下来,把它压进栈里。
- 10"e" 入栈,成为新的栈顶。栈从底到顶现在是 [l e e]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
- 11扫到第 3 位是普通字母 "t"。它不是星号,先暂时留下来,把它压进栈里。
- 12"t" 入栈,成为新的栈顶。栈从底到顶现在是 [l e e t]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
- 13扫到第 4 位是星号 *。它要删掉「左边最近、还活着」的字符,也就是当前栈顶 "t"。
- 14把栈顶 "t" 弹出去,星号 * 也随之消失。现在栈从底到顶是 [l e e]。
- 15扫到第 5 位是星号 *。它要删掉「左边最近、还活着」的字符,也就是当前栈顶 "e"。
- 16把栈顶 "e" 弹出去,星号 * 也随之消失。现在栈从底到顶是 [l e]。
- 17扫到第 6 位是普通字母 "c"。它不是星号,先暂时留下来,把它压进栈里。
- 18"c" 入栈,成为新的栈顶。栈从底到顶现在是 [l e c]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
- 19扫到第 7 位是普通字母 "o"。它不是星号,先暂时留下来,把它压进栈里。
- 20"o" 入栈,成为新的栈顶。栈从底到顶现在是 [l e c o]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
- 21扫到第 8 位是普通字母 "d"。它不是星号,先暂时留下来,把它压进栈里。
- 22"d" 入栈,成为新的栈顶。栈从底到顶现在是 [l e c o d]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
- 23扫到第 9 位是星号 *。它要删掉「左边最近、还活着」的字符,也就是当前栈顶 "d"。
- 24把栈顶 "d" 弹出去,星号 * 也随之消失。现在栈从底到顶是 [l e c o]。
- 25扫到第 10 位是普通字母 "e"。它不是星号,先暂时留下来,把它压进栈里。
- 26"e" 入栈,成为新的栈顶。栈从底到顶现在是 [l e c o e]。栈顶就是「左边最近、还活着」的字符,下一个 * 来了就删它。
- 27整串扫完。栈里从底到顶依次是 [l e c o e],拼起来就是答案 "lecoe"。每个字符只入栈或出栈一次,所以是线性时间。
⚠️ 容易写错的地方
✗ 错：遇到 * 还往栈里压
✓ 对：遇到 * 一律弹栈顶,绝不入栈
* 是删除操作不是字符,它要做的是把栈顶拿走
✗ 错：担心弹栈时栈是空的
✓ 对：题目保证每个 * 左边都有可删字符
约束已担保 * 出现时栈非空,不必额外判空(但工程里加判空更稳)
✗ 错：把栈顶当成原串的「前一个位置」
✓ 对：栈顶是「还活着的最后一个字符」
前面的字符可能已被别的 * 删掉,所以要看栈顶而不是原下标 i 减一
完整代码（Python / C++ / Java）
Python
class Solution:
def removeStars(self, s: str) -> str:
st = []
for ch in s:
if ch == '*':
st.pop()
else:
st.append(ch)
return ''.join(st)C++
#include <string>
using namespace std;
class Solution {
public:
string removeStars(string s) {
string st;
for (char c : s) {
if (c == '*') st.pop_back();
else st.push_back(c);
}
return st;
}
};Java
import java.util.*;
class Solution {
public String removeStars(String s) {
StringBuilder st = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == '*') st.deleteCharAt(st.length() - 1);
else st.append(c);
}
return st.toString();
}
}复杂度
时间
O(n)
n 是字符串长度,每个字符只被入栈或出栈一次,各做一次常数操作
空间
O(n)
最坏情况(没有星号)所有字符都进栈,栈的大小最多到 n
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 从字符串中移除星号 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
不用栈能做吗?+
能。可以用一个可变数组(或双指针 write 写指针)模拟栈:维护一个有效长度 len,普通字符写到 len 处并 len 加一,遇 * 就 len 减一。本质还是栈,只是省掉显式的栈结构,空间和时间不变。
C++ 里为什么能直接拿 string 当栈?+
string 的 push_back / pop_back 就是在末尾增删字符,末尾即栈顶,语义和栈完全一致,还省去额外容器和最后的拼接。Java 同理可用 StringBuilder 的 append / deleteCharAt(末位)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 从字符串中移除星号 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。