企业官网建设流程全解析

这道题是我cpp刷题打卡记录里的第3篇，选的题目是LeetCode 844：比较含退格的字符串。题目名字一眼看过去就是个字符串比较模拟题，但实际做下来会发现，它表面考栈，内里考的是你能不能把“退格”这个动作抽象成一个可逆的扫描过程。这篇文章把我的完整思考和实现过程记下来，包括开头用栈模拟的直观做法、后来为了O(1)空间写的反向双指针解法，以及我在这题边界条件下反复翻车的几个细节。

1. 先理解“退格键”到底删掉了什么

1.1 题意和最容易错的理解方式

题目要求：给定两个字符串 s 和 t，当它们分别被输入一个空白的文本编辑器后，判断二者是否相等。字符串中只包含小写字母和字符#，#代表退格键。退格键的作用是删除左侧的一个字符，如果左侧没有字符，这个退格操作会被忽略。

很多人的第一反应是“那我直接看两个字符串把#去掉之后是否相等不就行了？”这是不对的。比如s = "ab#c"，如果只删掉字符#，结果是"abc"；但实际输入过程是：先输入a得到a，输入b得到ab，按下退格键后b被删除，文本恢复到a，最后输入c，结果是"ac"。同理，t = "ad#c"的结果也是"ac"，所以两者相等。

这道题真正要比较的并不是“字符串的字面形式”，而是“字符串在编辑器里逐步输入后呈现的最终文本”。#不是普通字符，它是一个动作，它会影响它左侧紧邻的、还没有被其它#删除掉的字符。

我比较喜欢用“拿掉砖头”来理解：把字符串从左到右看成依次放进编辑器的一排砖头，每个#相当于一只拿走左侧最近砖头的手。如果左侧没有砖头可以拿，这只手就扑了个空，什么也不发生。连续两个#就是连续拿走左侧最近的两块砖头。注意这里的“最近”需要动态判断，因为前面的#可能已经拿走了一块砖头。

1.2 手算几个边界例子再开始写代码

我先自己列了张表，把容易出问题的输入都试了一遍，再动手写代码：

这个表看起来很基础，但它对后面写双指针版本特别有用。尤其是"a##c"和"#a#c"这种例子，容易让人误以为“开头的#会让结果不同”，实际两种输入方式最终都是"c"。

2. 解法一：用栈模拟输入过程，最直观也最不容易错

2.1 为什么栈和这道题天然匹配

从左到右输入字符串的时候，我们遇到的每个普通字符都是“追加到末尾”，每个#都是“删除末尾的一个已存在字符”。这正好符合栈的后进先出特性：后输入的字符在栈顶，退格时弹出的就是栈顶元素。

如果当前栈为空，也就是左侧没有字符可以删除，那这个退格操作直接忽略掉。注意这个分支很重要，很多人会把它漏掉，只写了pop，结果遇到s = "#a"这种输入时，空栈里做pop就会出问题。

更形象一点说：编辑器里正在编辑的文本，本质上就是一个栈。每次追加字符是push，每次退格是pop。所以写一个工具函数，把字符串按照真实输入顺序还原成最终文本，再直接比较两个最终文本是否相等，就是最朴素的解法。

2.2 一个极简的 C++ 实现

我们可以用std::string直接当栈用，因为它支持push_back和pop_back，而且最后还能直接用==比较。

string filter(string s) { string res; for (char c : s) { if (c == '#') { if (!res.empty()) { res.pop_back(); } } else { res.push_back(c); } } return res; } bool backspaceCompare(string s, string t) { return filter(s) == filter(t); }

这段代码只有十几行，逻辑也非常清晰：

• 遍历原始字符串；
• 遇到普通字符就入栈；
• 遇到#且栈不为空，就把栈顶弹出；
• 遇到#且栈为空，什么都不做；
• 最后比较两个栈的最终内容。

需要额外强调的是，pop_back()前必须判断!res.empty()。这里虽然用一个string来模拟栈，但它本质上和std::stack<char>完全一样，只是省掉了后续把栈内元素取出来重新组合的步骤。

2.3 这个解法的复杂度，以及它的问题在哪

时间复杂度是 O(m + n)，其中 m 和 n 分别是两个字符串的长度。每个字符最多入栈一次、出栈一次，所以每个字符的操作是常数时间，总时间必然是线性的。

空间复杂度也是 O(m + n)，因为filter(s)和filter(t)在最坏情况下（没有#，或者#被忽略）会分别保存长度接近原始字符串的结果。

这个解法能通过 LeetCode 的所有测试，我第一版也是这么写的。写完提交之后我盯着代码想了一会儿：如果面试官在看完这版之后问一句“能不能把额外空间降到 O(1)”，我要怎么接？

栈模拟法的本质缺陷是：我们为了比较最终结果，先完整保存了两份最终结果。但实际上，我们真的需要保存完整的最终文本吗？如果我在比较的过程中能一点一点地拿到“最终会留下的字符”，是不是就可以省掉存储？

这就引出了这道题更值得研究的地方：反向双指针。

3. 解法二：反向双指针，把“#”变成跳过计数器

3.1 为什么从后往前遍历会更容易

核心原因就在退格键的方向性上。从左往右输入时，#会删除“左边最近的字符”，这个“左边”是相对于当前已经输入的内容说的。如果正向遍历，我们必须记住前面所有还没被删除的字符，才能在某次遇到#时准确地删掉正确的那个字符，这本质上需要栈或者别的缓冲区。

但如果我们从右往左看这条字符串，情况会反过来：在一个#左边紧邻的字符是“会被它删除的候选者”。遇到#时，我们不急着去看左边是什么，而是先记下来“等一下要跳过左边一个字符”。如果左边又是一个#，那说明需要跳过的数量继续增加。跳过计数器的意义就是：右边已经出现了多少个还没被抵消的#。

为了方便理解，可以想象这样一个场景：一排字符从右向左依次经过检查员，检查员手里有一个计数器。看到一个#，他就把计数器加一，意思是“待会儿要作废一个普通字符”。看到一个普通字符时，如果计数器大于零，说明这个字符已经被右边的某个#宣判作废了，于是计数器减一，继续往左走。只有当计数器等于零时，这个普通字符才是最终能留在文本里的有效字符，才有资格拿出去和另一个字符串的有效字符做比较。

3.2 先在单个字符串上找“下一个有效字符”

我先把逻辑限制在一个字符串里，定义一个指针从字符串末尾开始往左移动，附带一个skip计数器。取下一个有效字符的过程是这样的：

• 如果当前字符是#，skip加一，指针往左移；
• 如果当前字符不是#，但skip大于零，说明这个字符会被右边某个#删除，skip减一，指针往左移；
• 如果当前字符不是#，且skip等于零，这个字符就是有效字符，停下来；
• 如果指针越界，说明这个字符串已经处理完了，当前没有有效字符。

这套逻辑和栈模拟的结果是等价的，只不过栈模拟是“从左往右动态删除”，这里变成了“从右往左静态跳过”。

在 C++ 里，这段查找过程可以直接写在主循环里：

int i = (int)s.size() - 1; int skipS = 0; while (i >= 0) { if (s[i] == '#') { skipS++; i--; } else if (skipS > 0) { skipS--; i--; } else { break; } }

循环结束后，i >= 0就表示找到了一个有效字符，并且这个有效字符就是s[i]；如果i < 0，说明已经没有有效字符了。

3.3 同时对比两个字符串的完整代码

对两个字符串做同样的处理，然后同步比较它们各自找出来的有效字符。完整代码我最终写成这样：

class Solution { public: bool backspaceCompare(string s, string t) { int i = (int)s.size() - 1; int j = (int)t.size() - 1; int skipS = 0; int skipT = 0; while (i >= 0 || j >= 0) { while (i >= 0) { if (s[i] == '#') { skipS++; i--; } else if (skipS > 0) { skipS--; i--; } else { break; } } while (j >= 0) { if (t[j] == '#') { skipT++; j--; } else if (skipT > 0) { skipT--; j--; } else { break; } } if (i >= 0 && j >= 0) { if (s[i] != t[j]) { return false; } } else if (i >= 0 || j >= 0) { return false; } i--; j--; } return true; } };

我来解释一下主循环的每一步都在干什么。

两个内层while分别把i和j移动到“下一个有效字符”的位置。如果某个字符串已经扫描完，对应的指针会变成负数。

比较阶段有三种情况：

• i >= 0 && j >= 0：两边都找到了有效字符，此时必须判断两个字符是否相等。如果不相等，两个字符串的最终结果一定不同，直接返回false；
• i >= 0 || j >= 0：只有一边还有有效字符，另一边已经扫描完，说明两个字符串的最终结果长度都不同，直接返回false；
• 两者都小于零：说明两边都已经没有剩余的有效字符，本次比较通过，继续看上一层字符。

注意每一轮比较完之后，必须执行i--; j--;，把当前已经比较过的有效字符跳过。这里的i、j是有符号的int，所以即使已经变成-1，继续减成-2也不会越界，只会让下一次外层while的i >= 0 || j >= 0条件更快变成假。

时间复杂度依然是 O(m + n)，因为每个字符仍然只会被扫描常数次。但是额外空间降到了 O(1)，只用了两个整数变量来记录下标和跳过次数。

3.4 双指针法为什么不会漏掉开头的“#”

继续拿s = "#a"举例。从右往左看，第一个是a，它很幸运，skipS是 0，所以a先被当作有效字符取出来比较；比较完之后i继续往左走到#，此时skipS变成 1，i变成-1。这个#虽然让skipS加了 1，但它的左边已经没有字符了，所以这个增加的计数实际上不会影响任何一个字符的有效性。

如果另一个字符串也扫描完了，整个函数返回true。这和s = "#a"实际结果为"a"是一致的。

如果两边剩余的有效字符个数不同，比如s = "a"，t = "#"，那么第一轮s会取出a，t在扫描到#后j变成-1，主循环走到else if (i >= 0 || j >= 0)时发现i >= 0，于是返回false。这同样正确："a"不等于空字符串。

4. 我实际写完以后，反复踩过的边界坑

4.1 空字符串和size_t的“暗算”

这是我第一次提交前不久差点踩进去的坑，也是 C++ 特有的问题。s.size()返回的是size_t，这是一个无符号整数类型。如果我写：

int i = s.size() - 1;

当s是空字符串时，s.size()等于 0，0 - 1在无符号整数运算里会变成了一个非常大的无符号数，再把它赋值给有符号的int，结果是实现相关的，通常不是你期望的-1，而是溢出或一个奇怪的值。一旦i不是-1，后面while (i >= 0)就可能变成一个近乎无限循环，或者访问越界。

更稳妥的写法是：

int i = (int)s.size() - 1; int j = (int)t.size() - 1;

先把无符号长度显式转成有符号int，再做减法。空字符串时的i和j就是正确的-1。这道题所给的输入可能有空字符串，LeetCode 的边界用例也会覆盖这种场景，所以这个细节不是吹毛求疵，是真的能让代码从“碰巧能跑”变成“逻辑严密”。

4.2 查找有效字符的while循环，条件顺序不能写反

第二种容易踩的坑，是把跳过逻辑简写得过于随意。比如有人会写成：

while (i >= 0 && (s[i] == '#' || skipS > 0)) { if (s[i] == '#') { skipS++; } else { skipS--; } i--; }

这个写法本身逻辑正确，因为循环条件里已经过滤掉了不需要处理的情况，但问题在于阅读时特别容易被误判成“只要遇到#就一直跳过”。我更推荐把三种情况展开写，也就是前面代码里的if / else if / else结构。看起来行数多一些，但实际上把“遇到#”“被跳过的普通字符”“真正的有效字符”三种状态分得很清，排查问题时一眼就能看出逻辑节点在哪里。

更隐蔽的错误是，把i--写进if和else if里，但在else分支忘记break，结果i永远停不下来。尤其是在第一个while内部还有嵌套处理时，这种死循环会非常难找。

4.3 比较结束后忘记了i--; j--;

这句话看起来多余，很多人会想：内层while不是已经把i和j移到有效字符上了吗？为什么还要额外移动一次？

因为内层循环是在“找到有效字符后立刻停止”的。此时i和j都停在有效字符上。如果下一轮还想继续找“更靠左的下一个有效字符”，就必须先把当前这个有效字符跨过去。如果没有这行i--; j--;，下一轮外层循环仍然会发现同样的有效字符，导致死循环。

这个操作在代码结构上最容易漏，因为它不在内层while的循环体里，而是在主循环靠近末尾的位置。我自己第一次写的时候也漏了，结果本地编译运行直接卡住，后来加了一行printf调试才发现i和j一直没变。

4.4 只比较到一方结束就返回，也是常见的逻辑坑

如果我在主循环里写的是：

while (i >= 0 && j >= 0) { // ... } return true;

那么遇到s = "ab"，t = "ab#c"这类情况，可能在i和j其中一个已经结束的时候就直接退出循环，返回true了。但实际最终文本可能不同："ab"不等于"ac"。所以循环条件必须是i >= 0 || j >= 0，只要还有一方没扫描完，就要继续处理，直到双方都结束为止。

4.5 用测试用例反复对照栈模拟和双指针的结果

写完双指针版本后，我没有直接提交，而是先用前面第一节列出的边界用例，在本地分别跑了一遍栈模拟版和双指针版，对比输出。

#include <iostream> #include <string> using namespace std; int main() { Solution sol; cout << sol.backspaceCompare("ab#c", "ad#c") << endl; // 1 cout << sol.backspaceCompare("ab##", "c#d#") << endl; // 1 cout << sol.backspaceCompare("a##c", "#a#c") << endl; // 1 cout << sol.backspaceCompare("a#c", "b") << endl; // 0 cout << sol.backspaceCompare("bxj##tw", "bxj###tw") << endl; // 0 return 0; }

这种“先写一个保证正确的版本，再拿它当参照物验证优化版本”的方法，在我自己的刷题过程里特别有用。尤其是字符串处理题，边界条件非常多，靠眼睛看代码很难看出问题，但用几组手算好的用例一测就立刻暴露了。

5. 从这题延伸出的同类问题套路

5.1 核心思维一：凡是“后输入的字符删除先输入字符”，优先想栈

这道题有一个非常明显的结构特征：字符按顺序追加，退格删除最近追加的字符。这和括号匹配、函数调用栈、浏览器返回键的“最近优先”逻辑是同构的。遇到这类题，先想栈模拟永远是最稳妥的方案，它能保证正确性，而且代码很简短。

LeetCode 上其他题目也有很多同款套路，比如 1047 题删除字符串中的所有相邻重复项，核心也是对相同字符做压栈和弹栈操作；再比如 71 题简化路径，同样可以用栈来处理..代表的目录回退。它们的共同点都是“当前操作只会影响最近的一个元素”。

5.2 核心思维二：当题目要求 O(1) 空间，就要试着从反方向扫描

栈模拟的代价是 O(n) 额外空间。如果面试官限制了空间，我们就得放弃“保存中间状态”的思路，想清楚问题的方向性。对于这种“删除左侧最近字符”的问题，反向遍历天然能避开存储问题。因为我们只需要用一个计数器记住右侧还有多少个删除操作没被消耗，而不需要真的记录被删除的字符是什么。

这个思维可以迁移到很多场景：当某个操作影响的是“已经处理过的内容”，尝试反向处理，往往能让原本需要缓冲区的逻辑变得只需要一个整数。和它类似的还有链表题目里的“从尾到头打印”“删除倒数第 k 个节点”这类反向遍历需求，本质上都是正着做需要缓存，反着做只需要位置信息。

5.3 如果题目变种成“连续删除 k 个字符”呢？

我们可以把这个思路做一个小扩展。假设题目不再是一个#删除一个字符，而是字符#k或某种标记代表连续删除左侧 k 个字符，那么反向扫描时的skip就不再是每次加一，而是每次加上 k，遇到普通字符且skip > 0时减一。

这相当于把“一次删除一个”升级为“一次删除多个”，但算法骨架完全不需要变化。栈模拟在这时候会显得比较笨重，因为一次可能要弹出很多个字符；而双向扫描加上skip计数器依然是 O(1) 空间，代码修改量极小。

5.4 如果题目改成了“编辑器里有光标，退格删除光标左侧”呢？

这种变体本质上就不再是普通的字符串线性比较问题了，因为字符的输入位置不再固定为末尾。遇到光标移动，我们需要维护一个可插入可删除的序列，复杂度会上一个台阶，通常用链表或者平衡树结构。LeetCode 844 之所以能保持简单，正是因为题目约定字符串是从左到右顺序输入到文本末尾，退格删除的是左侧最近字符，这让“栈”和“反向扫描”两个模型都成立。

所以以后再看到类似题目，先判断一件事：操作是否永远发生在“当前字符串末尾”？如果是，它就是栈模型；如果题目说可以移动光标再输入，那就不要硬套双指针反向扫描了，需要换数据结构。

5.5 这道题给我带来的实际刷题节奏启发

现在回到这篇文章记录的刷题过程本身。我第一遍提交用的是栈模拟，确认通过后花了大概二十分钟去推导双指针方案。整个过程我认为最高效的学习顺序不是“直接看最优解代码”，而是：

1. 先用最容易想到的方法 AC 一遍，确保对题意的理解不出偏差；
2. 把最终文本的边界例子全部手算一遍，尤其是空字符串、连续退格、退格键开头的场景；
3. 再问自己：如果限制空间，我要去掉哪些中间状态？需要从哪个方向扫描才能避免保存状态？
4. 最后用第一步写的正确版本去随机验证第二个版本的输出。

这样做比一上来就死记双指针模板要扎实得多。因为栈模拟版本能够提供大量可靠的测试输出，而双指针版本才是真正理解了题目本质之后的产物。如果你在准备面试或打周赛，先把栈模拟拿出来的好处还在于：即使时间不够写双指针，你也能保证这一题有分拿。至于反向扫描，那是确认自己有富余时间以后再去补的优化亮点。

再说一个我实际操作中的小技巧：如果直接用string模拟栈，别忘了在类里面把函数签名写成引用或传值都行，但 LeetCode 给的函数签名是backspaceCompare(string s, string t)，它是按值传参的，所以可以直接在传入的s、t上原地操作，避免额外的拷贝开销。如果改成写一个独立的filter函数，返回string会额外拷贝一次结果，但现代编译器通常会有返回值优化，不必担心到影响提交结果的程度。真正值得担心的只有空指针和下标越界，这两个问题在字符串题里出现的频率远高于性能问题。