LeetCode-Go 题解精讲：1047.Remove All Adjacent Duplicates In String 相邻重复字符消去（栈模拟“对对碰”）

LeetCode-Go 题解精讲1047.Remove All Adjacent Duplicates In String 相邻重复字符消去栈模拟“对对碰”【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文是 LeetCode-Go 题解仓库中 1047.Remove-All-Adjacent-Duplicates-In-String 一题的深度解析你将掌握题目约束、用单调栈消消乐式模拟相邻重复字符消除的核心思路以及仓库中 Go 实现的逐行拆解、复杂度分析与配套测试的运行方式并顺带对比同系列进阶题 1209删除 k 个相邻相同字符。题目回顾与约束给定一个由小写字母组成的字符串S重复项删除操作定义为选择两个相邻且相等的字母并删除它们。反复执行该操作直到无法继续删除为止最后返回结果字符串且题目保证最终答案唯一。以官方示例为例Input: abbaca Output: ca推导过程如下abbaca中bb相邻且相等删除后得到aacaaaca中aa相邻且相等删除后得到caca中不存在相邻且相等的字符停止最终结果为ca。题目约束来自 README1 S.length 20000S仅由英文小写字母组成。注意一个关键点每次删除后左右两侧子串会拼接在一起可能产生新的相邻重复对因此需要反复处理直到字符串中任意两个相邻字符都不相等为止。解题思路栈模拟“对对碰”本体的核心解法在 README 解题思路 中给出用栈模拟类似“对对碰”。具体规则依次扫描字符串中的每个字符新字符到来时与栈顶字符比较若栈为空或栈顶字符与新字符不相等则入栈若栈顶字符与新字符相等说明出现一对相邻重复直接弹出栈顶相当于把这两个字符一起删除扫描结束后栈中剩余字符即为最终答案。这种做法的正确性来源于栈天然保存了“当前结果串”的后缀。当删除一对字符后之前被压住的字符重新暴露为栈顶下一个字符会再次与它比较从而自动处理“删除后拼接产生的新重复”——这正是题目要求的反复消除语义。算法复杂度时间复杂度O(n)每个字符最多入栈一次、出栈一次空间复杂度O(n)栈中最多存放全部字符。相比于每删除一次就重建字符串的暴力法可能达到 O(n²)栈解法线性扫描一遍即可完成完美适配S.length 20000的规模。仓库源码逐行解析仓库中本题的实现位于 1047. Remove All Adjacent Duplicates In String.go完整代码如下package leetcode func removeDuplicates1047(S string) string { stack : []rune{} for _, s : range S { if len(stack) 0 || len(stack) 0 stack[len(stack)-1] ! s { stack append(stack, s) } else { stack stack[:len(stack)-1] } } return string(stack) }逐行解读stack : []rune{}初始化一个空栈。这里选择rune切片是因为for _, s : range S在 Go 中按rune迭代字符串天然兼容 Unicode 字符与栈元素类型保持一致入栈分支len(stack) 0 || len(stack) 0 stack[len(stack)-1] ! s。栈为空时直接入栈栈非空时只有当前字符与栈顶stack[len(stack)-1]不同才入栈出栈分支else 分支对应“当前字符与栈顶相同”通过stack stack[:len(stack)-1]弹出栈顶模拟删除这一对相邻重复字符return string(stack)扫描结束后把栈内剩余字符拼回字符串返回。实现细节上值得注意的两点入栈条件的len(stack) 0 前缀其实可以省略——运算符本身具备短路求值当栈为空时不会访问stack[len(stack)-1]。仓库保留该写法是为了让条件语义更显式、更易读出栈操作stack[:len(stack)-1]只是收缩切片长度底层数组仍被复用配合 Go 切片的 append 扩容机制整体依然保持 O(n) 的均摊时间复杂度。与“对撞删除”边界情况的核对空串虽然约束下限是 1栈为空直接返回空串全部重复如aaaa成对弹出后栈空返回无任何重复如abc每个字符都与栈顶不同全部入栈原样返回。测试用例与运行方式仓库为本题配套了测试文件 1047. Remove All Adjacent Duplicates In String_test.go采用question1047 / para1047 / ans1047的结构化组织方式与本仓库其他题目的测试风格一致package leetcode import ( fmt testing ) type question1047 struct { para1047 ans1047 } // para 是参数 // one 代表第一个参数 type para1047 struct { s string } // ans 是答案 // one 代表第一个答案 type ans1047 struct { one string } func Test_Problem1047(t *testing.T) { qs : []question1047{ { para1047{abbaca}, ans1047{ca}, }, } fmt.Printf(------------------------Leetcode Problem 1047------------------------\n) for _, q : range qs { _, p : q.ans1047, q.para1047 fmt.Printf(【input】:%v 【output】:%v\n, p, removeDuplicates1047(p.s)) } fmt.Printf(\n\n\n) }测试以官方示例abbaca - ca作为唯一用例通过removeDuplicates1047(p.s)调用被测函数并打印输入输出。由于Test_Problem1047内部没有显式t.Errorf断言仓库中大量题目采用“打印对比”的轻量测试风格读者可以自行将打印结果与期望输出比对。运行该测试的命令在本仓库根目录执行go test -v -run Test_Problem1047 ./leetcode/1047.Remove-All-Adjacent-Duplicates-In-String/如果希望运行全部 LeetCode 题解测试仓库根目录提供了 gotest.sh 脚本它会对./leetcode/...全量执行测试并生成合法的覆盖率文件go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...仓库根目录已存在 coverage.txt 覆盖率产物可见全量测试与覆盖率统计是该仓库的常规操作流程。扩展对比同系列进阶题 1209如果把“删除 2 个相邻相同字符”推广为“删除 k 个相邻相同字符”就是 LeetCode-Go 仓库中的进阶题 1209.Remove All Adjacent Duplicates in String II。两题的核心差异在于1047 只要栈顶与当前字符相同即弹栈而 1209 需要统计连续相同字符的个数只有计数达到k才触发删除。仓库中 1209 的栈解法见 1209. Remove All Adjacent Duplicates in String II.go在栈元素中同时保存字符与频次stack, arr : [][2]int{}, []byte{} for _, c : range s { i : int(c - a) if len(stack) 0 stack[len(stack)-1][0] i { stack[len(stack)-1][1] if stack[len(stack)-1][1] k { stack stack[:len(stack)-1] } } else { stack append(stack, [2]int{i, 1}) } }可以看到1209 中每个栈元素是[2]int[0]记录字符编号[1]记录该字符连续出现的次数当栈顶计数达到k时整体弹出。而 1047 可以看作k 2且无需计数的特例栈顶计数到 2 即弹出等价于“相同即弹”。吃透 1047 的栈思路再理解 1209 的“栈 计数”只是顺理成章的扩展。小结1047 题是栈这一数据结构的经典入门应用核心价值在于体会“栈顶暴露当前结果串后缀”这一性质如何天然支持删除后的反复拼接消除线性扫描 栈顶比较即可一次完成全部消除时间复杂度 O(n)、空间复杂度 O(n)仓库的 Go 实现 仅 12 行简洁且可直接运行测试验证理解本题后可继续挑战 1209 题删除 k 个相邻相同字符以及 0020. Valid Parentheses括号匹配等同属“栈 相邻比较”家族的问题。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考