LeetCode 1047 删除字符串中的所有相邻重复项:C++ 栈与字符串双解法详解

原创2026-10-13 21:56:321,940 阅读
文章标签:教程

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 核心考点:相邻重复删除的「消消乐」性质

这道题的关键在于:删除一组相邻重复项之后,删除位置左侧和右侧的字符会重新相邻,可能再次构成新的重复项。

以示例为例:

  1. 第一轮:a b b a c a,删除 bb,得到 a a c a;
  2. 第二轮:a a c a 中 aa 又相邻了,继续删除,得到 c a;
  3. 第三轮: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 逐步拆解

  1. 提前返回:if (S.size() <= 1) return S;——长度 0 或 1 的字符串不可能存在相邻重复对,直接返回即可,这也是常见的边界剪枝写法。
  2. 入栈 / 出栈决策:遍历字符串的每一个字符 a:
    • 栈为空:直接 push;
    • 栈非空且 a == result.top():说明与栈顶字符重复,pop 抵消;
    • 栈非空且 a != result.top():push 入栈。
  3. 出栈拼串 + 反转:栈是后进先出结构,从栈顶依次取出的字符顺序与答案相反,因此必须 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 版本有两点结构性优势:

  1. 省去一次反转遍历:res 本身就是按栈底 → 栈顶的正确顺序累积的,不需要最后再 reverse。因为每次新字符都是追加在尾部,最终 res 的字符顺序天然就是正确答案。
  2. 连续内存、缓存友好: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 两题佐证了思路的迁移路径,可直接进入对应页面继续刷题验证。

登录后查看全文
InterviewGuide