 空间优化)
LeetCode 844. Backspace String Compare 题解用栈模拟退格键的 Go 实现与 O(1) 空间优化【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 844 题《Backspace String Compare比较含退格的字符串》展开以 LeetCode-Go 仓库中该题目的 README.md 为核心骨架结合仓库内 Go 源码实现 与 单元测试完整讲解题面、示例、约束、栈模拟解法及其复杂度并讨论题目 Follow up 中 O(N) 时间、O(1) 空间的经典优化思路。读完本文你将掌握退格键这一类字符回退问题的标准建模方式并能用 Go 快速写出可运行、可测试的解法。题目描述给定两个字符串S和T当它们分别被输入到空的文本编辑器中时判断二者最终是否相等。字符#表示退格键backspace。Input: S ab#c, T ad#c Output: true Explanation: Both S and T become ac.原题地址参见 LeetCode 844。示例仓库文档给出了 4 组典型用例覆盖了退格删空连续退格退格无效等关键场景示例 1普通退格Input: S ab#c, T ad#c Output: true Explanation: Both S and T become ac.S输入a b # cb被#退格删除最终为acT输入a d # cd被#删除最终同样为ac。示例 2全部退格删空Input: S ab##, T c#d# Output: true Explanation: Both S and T become .S输入a b # #两个#依次删除b、a最终为空串T输入c # d #最终同样为空串。示例 3开头即退格退格空栈无效Input: S a##c, T #a#c Output: true Explanation: Both S and T become c.S的第二个#作用于空文本不产生任何效果T的第一个#同样作用于空文本被忽略。示例 4结果不同Input: S a#c, T b Output: false Explanation: S becomes c while T becomes b.S的a被退格删除后剩cT就是b二者不相等。约束条件1 S.length 2001 T.length 200S和T仅包含小写字母与#字符两个字符串的长度均不超过 200因此任何 O(N²) 量级以内的暴力做法在本题数据范围内都不会超时但题目在 Follow up 中明确要求更优解见下文进阶一节。题目大意给 2 个字符串如果遇到#号字符就回退删除一个字符。问最终的 2 个字符串是否完全一致。这道题的核心建模是#不是普通字符而是一个删除前一个已输入字符的操作符。因此判断两个字符串是否相等不能直接比较原始串而必须先对两个串分别执行完整的模拟打字过程得到最终的有效文本再比较结果。解题思路栈模拟仓库文档给出的解法思路非常直接用栈的思想来模拟遇到#字符就回退一个字符不是#号就入栈一个字符最后比较两个栈的最终内容即可。这一思路的物理直觉与真实编辑器完全一致文本编辑器中维护的是一个字符序列输入普通字符等价于在序列末尾追加入栈按退格键等价于删除序列末尾的字符出栈在空文本上按退格键没有任何效果空栈弹栈需跳过。仓库源码实现LeetCode-Go 仓库在 844. Backspace String Compare.go 中给出了如下实现package leetcode func backspaceCompare(S string, T string) bool { s : make([]rune, 0) for _, c : range S { if c # { if len(s) 0 { s s[:len(s)-1] } } else { s append(s, c) } } s2 : make([]rune, 0) for _, c : range T { if c # { if len(s2) 0 { s2 s2[:len(s2)-1] } } else { s2 append(s2, c) } } return string(s) string(s2) }实现细节说明用[]rune切片充当栈append(s, c)完成入栈s s[:len(s)-1]完成出栈与 Go 语言中切片模拟栈的标准写法一致可对比仓库中 20. Valid Parentheses.go 对括号匹配的同类栈处理。空栈退格保护遇到#时先判断len(s) 0只有栈非空才弹出栈顶。这一点对应示例 3 中在空文本上按退格键无效的语义是本题最容易遗漏的边界分支。rune而非byte源码使用for _, c : range S按 rune 迭代天然兼容多字节字符虽然本题约束输入仅为小写字母但该写法更稳健。最终比较将两个切片分别转换为字符串后以比较得到布尔结果。复杂度分析时间复杂度O(N)。其中N max(len(S), len(T))两个字符串各被完整扫描一遍每次入栈/出栈都是 O(1) 操作。空间复杂度O(N)。最坏情况下字符串不含任何#两个栈分别保存了全部字符因此额外空间与输入规模线性相关。边界情况梳理根据源码与测试用例本题需要覆盖的边界情况主要有三类边界场景示例预期行为连续退格直到清空S ab##, T c#d#两个栈均被弹空最终都为空串返回true栈为空时遇到#S #a#c, T #a#c空栈不弹栈#被忽略返回true退格后结果不同S a#c, T b栈内容分别为c与b返回false测试验证仓库为该题提供了完整的单元测试位于 844. Backspace String Compare_test.go其中Test_Problem844以表驱动方式覆盖了 README 中的全部 4 组用例qs : []question844{ {para844{ab#c, ad#c}, ans844{true}}, {para844{ab##, c#d#}, ans844{true}}, {para844{a##c, #a#c}, ans844{true}}, {para844{a#c, b}, ans844{false}}, }测试结构遵循仓库统一的question para ans表驱动约定para844封装输入参数s、tans844封装期望输出one便于批量断言与扩展新用例。整个仓库的测试通过根目录 gotest.sh 脚本驱动该脚本对全部题解包执行覆盖率收集go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...因此你也可以在仓库根目录直接运行bash gotest.sh或在单个题目目录下执行go test验证 844 题解的行为项目go.mod声明使用 Go 1.19运行前请确保本地 Go 版本不低于该要求。进阶如何做到 O(N) 时间、O(1) 空间原文档在 Follow up 中提出了一个经典问题能否在 O(N) 时间、O(1) 空间内解决栈模拟虽然时间已达 O(N)但空间仍是 O(N)。要压缩到 O(1) 额外空间常规思路是双指针从后向前扫描从两个字符串的末尾同时向前遍历各自维护一个待退格计数遇到#时退格计数1指针继续左移遇到普通字符时若计数大于 0则说明该字符会被后续的#删除计数-1、指针继续左移否则该字符就是最终存活的有效字符停下来比较若两个指针找到的有效字符不同直接返回false若相同两个指针同时继续左移重复上述过程两个字符串都扫描完毕后返回true。该算法全程只用常数额外变量时间仍为线性空间降为 O(1)。需要说明的是O(1) 空间解法是题目 Follow up 提出的优化目标仓库当前只收录了上文展示的栈模拟实现读者可将双指针写法作为练习自行实现并对照测试用例验证。小结844 题是模拟题 栈的典型代表解题关键在于正确理解#的退格语义尤其是空栈退格无效果这一边界。仓库提供的 Go 实现以[]rune切片模拟栈代码简洁、行为与真实编辑器一致并通过表驱动测试完整覆盖了题目给出的全部示例。若追求极端空间效率可再按 Follow up 的思路改写为双指针版本将空间复杂度从 O(N) 降到 O(1)。题目文档leetcode/0844.Backspace-String-Compare/README.md题解源码844. Backspace String Compare.go单元测试844. Backspace String Compare_test.go同类栈题参考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），仅供参考 
长河君 · 2026/9/12 14:06:17 · 阅读 1.2k LeetCode 844. Backspace String Compare 题解：用栈模拟退格键的 Go 实现与 O(1) 空间优化
LeetCode 844. Backspace String Compare 题解用栈模拟退格键的 Go 实现与 O(1) 空间优化【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 844 题《Backspace String Compare比较含退格的字符串》展开以 LeetCode-Go 仓库中该题目的 README.md 为核心骨架结合仓库内 Go 源码实现 与 单元测试完整讲解题面、示例、约束、栈模拟解法及其复杂度并讨论题目 Follow up 中 O(N) 时间、O(1) 空间的经典优化思路。读完本文你将掌握退格键这一类字符回退问题的标准建模方式并能用 Go 快速写出可运行、可测试的解法。题目描述给定两个字符串S和T当它们分别被输入到空的文本编辑器中时判断二者最终是否相等。字符#表示退格键backspace。Input: S ab#c, T ad#c Output: true Explanation: Both S and T become ac.原题地址参见 LeetCode 844。示例仓库文档给出了 4 组典型用例覆盖了退格删空连续退格退格无效等关键场景示例 1普通退格Input: S ab#c, T ad#c Output: true Explanation: Both S and T become ac.S输入a b # cb被#退格删除最终为acT输入a d # cd被#删除最终同样为ac。示例 2全部退格删空Input: S ab##, T c#d# Output: true Explanation: Both S and T become .S输入a b # #两个#依次删除b、a最终为空串T输入c # d #最终同样为空串。示例 3开头即退格退格空栈无效Input: S a##c, T #a#c Output: true Explanation: Both S and T become c.S的第二个#作用于空文本不产生任何效果T的第一个#同样作用于空文本被忽略。示例 4结果不同Input: S a#c, T b Output: false Explanation: S becomes c while T becomes b.S的a被退格删除后剩cT就是b二者不相等。约束条件1 S.length 2001 T.length 200S和T仅包含小写字母与#字符两个字符串的长度均不超过 200因此任何 O(N²) 量级以内的暴力做法在本题数据范围内都不会超时但题目在 Follow up 中明确要求更优解见下文进阶一节。题目大意给 2 个字符串如果遇到#号字符就回退删除一个字符。问最终的 2 个字符串是否完全一致。这道题的核心建模是#不是普通字符而是一个删除前一个已输入字符的操作符。因此判断两个字符串是否相等不能直接比较原始串而必须先对两个串分别执行完整的模拟打字过程得到最终的有效文本再比较结果。解题思路栈模拟仓库文档给出的解法思路非常直接用栈的思想来模拟遇到#字符就回退一个字符不是#号就入栈一个字符最后比较两个栈的最终内容即可。这一思路的物理直觉与真实编辑器完全一致文本编辑器中维护的是一个字符序列输入普通字符等价于在序列末尾追加入栈按退格键等价于删除序列末尾的字符出栈在空文本上按退格键没有任何效果空栈弹栈需跳过。仓库源码实现LeetCode-Go 仓库在 844. Backspace String Compare.go 中给出了如下实现package leetcode func backspaceCompare(S string, T string) bool { s : make([]rune, 0) for _, c : range S { if c # { if len(s) 0 { s s[:len(s)-1] } } else { s append(s, c) } } s2 : make([]rune, 0) for _, c : range T { if c # { if len(s2) 0 { s2 s2[:len(s2)-1] } } else { s2 append(s2, c) } } return string(s) string(s2) }实现细节说明用[]rune切片充当栈append(s, c)完成入栈s s[:len(s)-1]完成出栈与 Go 语言中切片模拟栈的标准写法一致可对比仓库中 20. Valid Parentheses.go 对括号匹配的同类栈处理。空栈退格保护遇到#时先判断len(s) 0只有栈非空才弹出栈顶。这一点对应示例 3 中在空文本上按退格键无效的语义是本题最容易遗漏的边界分支。rune而非byte源码使用for _, c : range S按 rune 迭代天然兼容多字节字符虽然本题约束输入仅为小写字母但该写法更稳健。最终比较将两个切片分别转换为字符串后以比较得到布尔结果。复杂度分析时间复杂度O(N)。其中N max(len(S), len(T))两个字符串各被完整扫描一遍每次入栈/出栈都是 O(1) 操作。空间复杂度O(N)。最坏情况下字符串不含任何#两个栈分别保存了全部字符因此额外空间与输入规模线性相关。边界情况梳理根据源码与测试用例本题需要覆盖的边界情况主要有三类边界场景示例预期行为连续退格直到清空S ab##, T c#d#两个栈均被弹空最终都为空串返回true栈为空时遇到#S #a#c, T #a#c空栈不弹栈#被忽略返回true退格后结果不同S a#c, T b栈内容分别为c与b返回false测试验证仓库为该题提供了完整的单元测试位于 844. Backspace String Compare_test.go其中Test_Problem844以表驱动方式覆盖了 README 中的全部 4 组用例qs : []question844{ {para844{ab#c, ad#c}, ans844{true}}, {para844{ab##, c#d#}, ans844{true}}, {para844{a##c, #a#c}, ans844{true}}, {para844{a#c, b}, ans844{false}}, }测试结构遵循仓库统一的question para ans表驱动约定para844封装输入参数s、tans844封装期望输出one便于批量断言与扩展新用例。整个仓库的测试通过根目录 gotest.sh 脚本驱动该脚本对全部题解包执行覆盖率收集go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...因此你也可以在仓库根目录直接运行bash gotest.sh或在单个题目目录下执行go test验证 844 题解的行为项目go.mod声明使用 Go 1.19运行前请确保本地 Go 版本不低于该要求。进阶如何做到 O(N) 时间、O(1) 空间原文档在 Follow up 中提出了一个经典问题能否在 O(N) 时间、O(1) 空间内解决栈模拟虽然时间已达 O(N)但空间仍是 O(N)。要压缩到 O(1) 额外空间常规思路是双指针从后向前扫描从两个字符串的末尾同时向前遍历各自维护一个待退格计数遇到#时退格计数1指针继续左移遇到普通字符时若计数大于 0则说明该字符会被后续的#删除计数-1、指针继续左移否则该字符就是最终存活的有效字符停下来比较若两个指针找到的有效字符不同直接返回false若相同两个指针同时继续左移重复上述过程两个字符串都扫描完毕后返回true。该算法全程只用常数额外变量时间仍为线性空间降为 O(1)。需要说明的是O(1) 空间解法是题目 Follow up 提出的优化目标仓库当前只收录了上文展示的栈模拟实现读者可将双指针写法作为练习自行实现并对照测试用例验证。小结844 题是模拟题 栈的典型代表解题关键在于正确理解#的退格语义尤其是空栈退格无效果这一边界。仓库提供的 Go 实现以[]rune切片模拟栈代码简洁、行为与真实编辑器一致并通过表驱动测试完整覆盖了题目给出的全部示例。若追求极端空间效率可再按 Follow up 的思路改写为双指针版本将空间复杂度从 O(N) 降到 O(1)。题目文档leetcode/0844.Backspace-String-Compare/README.md题解源码844. Backspace String Compare.go单元测试844. Backspace String Compare_test.go同类栈题参考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），仅供参考