这道题是我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 手算几个边界例子再开始写代码我先自己列了张表把容易出问题的输入都试了一遍再动手写代码输入 s输入 t实际结果说明ab#cad#cacvsac返回 true最直观的基础示例ab##c#d#vs返回 true两个字符串都可能被删空a##c#a#ccvsc返回 true开头的#没有字符可删会被忽略a#cbcvsb返回 false退格会改变原本看似相同的前缀bxj##twbxj###twbtwvstw返回 false退格数量超过已输入字符时会继续把更早的字符也删掉这个表看起来很基础但它对后面写双指针版本特别有用。尤其是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::stackchar完全一样只是省掉了后续把栈内元素取出来重新组合的步骤。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两边都找到了有效字符此时必须判断两个字符是否相等。如果不相等两个字符串的最终结果一定不同直接返回falsei 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变成 1i变成-1。这个#虽然让skipS加了 1但它的左边已经没有字符了所以这个增加的计数实际上不会影响任何一个字符的有效性。如果另一个字符串也扫描完了整个函数返回true。这和s #a实际结果为a是一致的。如果两边剩余的有效字符个数不同比如s at #那么第一轮s会取出at在扫描到#后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()等于 00 - 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 abt 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 这道题给我带来的实际刷题节奏启发现在回到这篇文章记录的刷题过程本身。我第一遍提交用的是栈模拟确认通过后花了大概二十分钟去推导双指针方案。整个过程我认为最高效的学习顺序不是“直接看最优解代码”而是先用最容易想到的方法 AC 一遍确保对题意的理解不出偏差把最终文本的边界例子全部手算一遍尤其是空字符串、连续退格、退格键开头的场景再问自己如果限制空间我要去掉哪些中间状态需要从哪个方向扫描才能避免保存状态最后用第一步写的正确版本去随机验证第二个版本的输出。这样做比一上来就死记双指针模板要扎实得多。因为栈模拟版本能够提供大量可靠的测试输出而双指针版本才是真正理解了题目本质之后的产物。如果你在准备面试或打周赛先把栈模拟拿出来的好处还在于即使时间不够写双指针你也能保证这一题有分拿。至于反向扫描那是确认自己有富余时间以后再去补的优化亮点。再说一个我实际操作中的小技巧如果直接用string模拟栈别忘了在类里面把函数签名写成引用或传值都行但 LeetCode 给的函数签名是backspaceCompare(string s, string t)它是按值传参的所以可以直接在传入的s、t上原地操作避免额外的拷贝开销。如果改成写一个独立的filter函数返回string会额外拷贝一次结果但现代编译器通常会有返回值优化不必担心到影响提交结果的程度。真正值得担心的只有空指针和下标越界这两个问题在字符串题里出现的频率远高于性能问题。 LeetCode 844：从栈模拟到双指针，详解含退格字符串比较
这道题是我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 手算几个边界例子再开始写代码我先自己列了张表把容易出问题的输入都试了一遍再动手写代码输入 s输入 t实际结果说明ab#cad#cacvsac返回 true最直观的基础示例ab##c#d#vs返回 true两个字符串都可能被删空a##c#a#ccvsc返回 true开头的#没有字符可删会被忽略a#cbcvsb返回 false退格会改变原本看似相同的前缀bxj##twbxj###twbtwvstw返回 false退格数量超过已输入字符时会继续把更早的字符也删掉这个表看起来很基础但它对后面写双指针版本特别有用。尤其是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::stackchar完全一样只是省掉了后续把栈内元素取出来重新组合的步骤。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两边都找到了有效字符此时必须判断两个字符是否相等。如果不相等两个字符串的最终结果一定不同直接返回falsei 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变成 1i变成-1。这个#虽然让skipS加了 1但它的左边已经没有字符了所以这个增加的计数实际上不会影响任何一个字符的有效性。如果另一个字符串也扫描完了整个函数返回true。这和s #a实际结果为a是一致的。如果两边剩余的有效字符个数不同比如s at #那么第一轮s会取出at在扫描到#后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()等于 00 - 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 abt 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 这道题给我带来的实际刷题节奏启发现在回到这篇文章记录的刷题过程本身。我第一遍提交用的是栈模拟确认通过后花了大概二十分钟去推导双指针方案。整个过程我认为最高效的学习顺序不是“直接看最优解代码”而是先用最容易想到的方法 AC 一遍确保对题意的理解不出偏差把最终文本的边界例子全部手算一遍尤其是空字符串、连续退格、退格键开头的场景再问自己如果限制空间我要去掉哪些中间状态需要从哪个方向扫描才能避免保存状态最后用第一步写的正确版本去随机验证第二个版本的输出。这样做比一上来就死记双指针模板要扎实得多。因为栈模拟版本能够提供大量可靠的测试输出而双指针版本才是真正理解了题目本质之后的产物。如果你在准备面试或打周赛先把栈模拟拿出来的好处还在于即使时间不够写双指针你也能保证这一题有分拿。至于反向扫描那是确认自己有富余时间以后再去补的优化亮点。再说一个我实际操作中的小技巧如果直接用string模拟栈别忘了在类里面把函数签名写成引用或传值都行但 LeetCode 给的函数签名是backspaceCompare(string s, string t)它是按值传参的所以可以直接在传入的s、t上原地操作避免额外的拷贝开销。如果改成写一个独立的filter函数返回string会额外拷贝一次结果但现代编译器通常会有返回值优化不必担心到影响提交结果的程度。真正值得担心的只有空指针和下标越界这两个问题在字符串题里出现的频率远高于性能问题。