LeetCode 1047 删除字符串中的所有相邻重复项:C++ 栈与字符串双解法详解
LeetCode 1047 删除字符串中的所有相邻重复项:C++ 栈与字符串双解法详解
本篇是 InterviewGuide 仓库「精选力扣 300+ 题目之栈」系列中 Easy 级别题目的技术解析,原始刷题笔记位于 docs/notes/03-hunting_job/03-algorithm/03-leetcode/07-栈/easy/1047.删除字符串中的所有相邻重复项.md。本文将完整继承原笔记的两版 C++ 解法,并从「为什么用栈」「为什么需要反转」「为什么用 string 更快」三个角度做源码级剖析,同时延伸到本仓库同主题的 844.比较含退格的字符串 与 1209.删除字符串中的所有相邻重复项 II,帮助你在校招/社招面试中彻底吃透这一类「相邻重复删除」问题。
一、题目理解:为什么这道题天生属于栈
1.1 题目描述
给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串,答案保证唯一。
1.2 示例
输入:"abbaca"
输出:"ca"
解释:例如,在 "abbaca" 中,我们可以删除 "bb",因为两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。
1.3 约束条件
1 <= S.length <= 20000
S 仅由小写英文字母组成
1.4 核心考点:相邻重复删除的「消消乐」性质
这道题的关键在于:删除一组相邻重复项之后,删除位置左侧和右侧的字符会重新相邻,可能再次构成新的重复项。
以示例为例:
- 第一轮:
a b b a c a,删除bb,得到a a c a; - 第二轮:
a a c a中aa又相邻了,继续删除,得到c a; - 第三轮:
c与a不相邻且不相同,无法继续删除,最终答案为ca。
这种「后删除的结果依赖于前一次删除」的链式反应,正是栈(后进先出,LIFO)的天然适用场景:
- 栈顶元素代表「当前尚未被抵消的最后一个字符」;
- 新字符到来时,只需与栈顶比较一次:相同则抵消(出栈),不同则入栈;
- 删除造成的新相邻关系,会在后续字符入栈时被自动、正确处理,无需回头扫描。
在 InterviewGuide 仓库的分类体系中,本题被归入栈分类的 Easy 级别。整个 LeetCode 刷题专栏按照数组、字符串、链表、栈、树、动态规划等 13 个标签组织,每类再分 Easy / Medium / Hard 三档,详情见专栏使用指南。
二、解法一:显式栈 stack<char>(原笔记第一版)
原笔记第一版使用标准库 std::stack<char> 显式模拟整个过程,完整代码如下:
string removeDuplicates(string S) {
if (S.size() <= 1) return S;
stack<char> result;
for (auto a : S) {
if (result.empty()) {
result.push(a);
}
else{
if (a == result.top())
result.pop();
else
result.push(a);
}
}
S = "";
while (!result.empty()) {
S += result.top();
result.pop();
}
reverse(S.begin(), S.end());//注意要反转才是正确结果
return S;
}
2.1 逐步拆解
- 提前返回:
if (S.size() <= 1) return S;——长度 0 或 1 的字符串不可能存在相邻重复对,直接返回即可,这也是常见的边界剪枝写法。 - 入栈 / 出栈决策:遍历字符串的每一个字符
a:- 栈为空:直接
push; - 栈非空且
a == result.top():说明与栈顶字符重复,pop抵消; - 栈非空且
a != result.top():push入栈。
- 栈为空:直接
- 出栈拼串 + 反转:栈是后进先出结构,从栈顶依次取出的字符顺序与答案相反,因此必须
reverse一次才是正确结果。
2.2 为什么一定要 reverse
这是本解法最容易写错的一步。假设输入为 "abbaca":
- 处理
a:栈为[a]; - 处理
b:栈为[a, b]; - 处理
b:与栈顶b相同,出栈,栈为[a]; - 处理
a:与栈顶a相同,出栈,栈为空; - 处理
c:栈为[c]; - 处理
a:与栈顶c不同,入栈,栈为[c, a]。
此时如果直接从栈顶拼接,得到的是 "ac",而正确答案是 "ca"(栈底 → 栈顶的顺序)。出栈顺序天然是逆序,所以代码末尾的 reverse 必不可少,这也是原笔记注释「注意要反转才是正确结果」的由来。
2.3 当时的提交表现
原笔记记录了当时提交的统计(注:LeetCode 评测结果会随提交时间、评测环境波动,以下数据仅代表当时的记录,仅供参考):
执行用时 :32 ms, 在所有 C++ 提交中击败了63.22%的用户
内存消耗 :12.1 MB, 在所有 C++ 提交中击败了100.00%的用户
显式栈版本需要额外维护一个 stack 容器,且出栈后还要多做一次反转遍历,这是它在时间上不如解法二的根本原因。
三、解法二:用 string 充当栈(原笔记第二版,推荐)
原笔记第二版换了一个思路:直接用 string 当作栈来用。string 天然支持尾插、取尾、尾删三个操作,恰好对应栈的 push、top、pop:
string removeDuplicates(string S) {
string res = "";
for(char c: S)
if(res.size() && res.back() == c)
res.pop_back();
else
res += c;
return res;
}
3.1 对应关系与流程
| 栈操作 | string 模拟写法 | 语义 |
|---|---|---|
| 判空 | res.size()(为 0 则空) |
栈是否为空 |
| 取栈顶 | res.back() |
当前最后一个未被抵消的字符 |
| 入栈 | res += c |
压入新字符 |
| 出栈 | res.pop_back() |
抵消栈顶字符 |
核心循环逻辑与解法一一对应:
- 若
res非空且res.back() == c:说明新字符与「栈顶」重复,pop_back()抵消; - 否则:
res += c,把字符压入「栈」中。
3.2 为什么它更快
相比显式 stack<char>,string 版本有两点结构性优势:
- 省去一次反转遍历:
res本身就是按栈底 → 栈顶的正确顺序累积的,不需要最后再reverse。因为每次新字符都是追加在尾部,最终res的字符顺序天然就是正确答案。 - 连续内存、缓存友好:
std::string的元素存储在连续内存上,push_back/pop_back/back都是对尾部元素的直接操作,开销极小;而std::stack底层默认容器是std::deque,还存在额外的容器抽象与迭代开销。
原笔记同样记录了该版本的提交表现:
执行用时 :12 ms, 在所有 C++ 提交中击败了99.59%的用户
内存消耗 :12.4 MB, 在所有 C++ 提交中击败了100.00%的用户
从 32 ms 到 12 ms,仅通过把显式栈换成 string 栈,耗时提升约 2.7 倍,这正印证了「简单数据结构 + 连续内存」在工程与算法题中的实际价值。
四、复杂度分析与边界情况
4.1 复杂度
两种解法都只对字符串扫描一遍,每字符最多入栈一次、出栈一次:
- 时间复杂度:O(n),其中 n 为字符串长度;
- 空间复杂度:O(n),栈中最多存放 n 个字符(例如输入无任何相邻重复对时)。
4.2 边界情况
- 空串
""→ 返回""; - 单字符
"a"→ 返回"a"(第一版有S.size() <= 1提前返回); - 全部相同字符,如
"aaaa"→ 依次抵消,返回""; - 无任何相邻重复,如
"abcd"→ 每个字符依次入栈,原样返回"abcd"。
五、同主题延伸:一套思路吃透一个题族
「用栈处理相邻重复删除」这套思路在 InterviewGuide 仓库的栈分类中反复出现,可以作为举一反三的配套练习:
5.1 844. 比较含退格的字符串
给定 S 和 T 两个字符串,# 代表退格字符,判断二者经过退格处理后是否相等。原笔记在该题的第一版注释中明确写道「学 1047 题的 string 作为栈的方法」——处理 # 时从「栈」尾部 pop_back 一个字符,处理普通字母时 += 入栈,最后比较两个 string 是否相等。这几乎是 1047 的解法模板直接迁移,可见「string 当作栈」在同类问题中的通用性。
5.2 1209. 删除字符串中的所有相邻重复项 II
这是 1047 的升级版:不再是固定删除 2 个相邻相同字符,而是每次删除 k 个相邻且相等的字符(2 <= k <= 10^4,字符串长度可达 10^5)。原笔记给出的解法将「字符栈」升级为双栈:stack<char> 保存字符,stack<int> 保存每个字符的连续出现次数。入栈时若与栈顶字符相同则计数 ++times.top(),一旦计数达到 k 就同时弹出字符栈与计数栈。这也解释了 1047 为什么会出现在 Easy 档、而 1209 被划入 Medium 档——核心思路同源,区别只在于是否需要对「连续相同字符的计数」做额外维护。
5.3 同类题目列表
在栈分类目录中还可以找到更多栈应用题,例如 155. 最小栈(双栈同步维护最小值)、71. 简化路径 等,均可用「栈顶即答案前缀的最后一个元素」这一视角统一理解。
六、面试视角小结
- 一句话抓住考点:凡是「相邻元素重复即删除 / 抵消 / 退格」类的题目,第一反应都应该是栈——栈顶就是天然的比较对象,删除后的新相邻关系会在后续入栈时被自动处理。
- 优先给出 string 版本:面试中建议直接写出解法二,它不仅代码更短(无需
reverse),还顺便展示了「用连续内存容器模拟栈」的优化意识,比背模板的显式栈写法更能体现功底。 - 追问方向:进阶考察可能问能否做到 O(1) 额外空间(例如使用原地双指针覆盖技巧,将结果写回原字符串的前缀位置),可结合本题约束(
S.length <= 20000)与 1209 的计数场景做进一步思考。
本篇内容完全围绕本仓库原始刷题笔记展开,两版解法代码、题目示例与约束、当时的提交统计均忠实继承原文档;结合仓库中同分类的 844、1209 两题佐证了思路的迁移路径,可直接进入对应页面继续刷题验证。