LeetCode 844. 比较含退格的字符串
目录
题目描述
题意分析
两个字符串里的
#表示退格键：输入到这里时会删掉前面已经输入的一个字符；如果前面已经没有字符了，退格什么也不做。问两个串按这个规则「打」完之后，最终文本是否相同。第一个容易读漏的点是
#的作用对象是已经处理完的结果，不是原串里紧邻的那个字符。比如"ab##"中第一个#删掉b，第二个#删掉a，最终为空串；而"a#b#"也是空串。多个#会连续消耗多个字符，退格数必须能累积。第二个点是退格作用在空文本上要静默忽略，不能越界，也不能「欠账」。
"###abc"的结果就是"abc"，前三个退格全部落空。约束里串长最大 200，$O(n)$ 或 $O(n + m)$ 的任何做法都够用。真正决定这题档次的是进阶要求：能否做到 $O(1)$ 额外空间。这句话直接排除了「先构造出两个最终串再比较」的思路，把题目从模拟题变成了双指针题。
边界：两个串长度可以不同（
"a#c"与"b#c"都归约成"c"，答案为真）；退格后可能一方先耗尽，另一方还有剩余有效字符，此时必须判为不等；两边都归约成空串则相等。
解法：双指针从后往前跳过退格
核心思路
最直接的写法是用栈：从左到右扫，遇到普通字符压栈，遇到
#就在栈非空时弹出一个，扫完把两个栈的内容比一比。这个做法思路清晰、绝不会写错，但它需要 $O(n + m)$ 的额外空间来保存归约后的文本，卡在了进阶要求上。瓶颈在哪？在于从左往右扫时，你不知道当前这个字符将来会不会被后面的
#删掉，所以只能先存着。信息的流向和遍历方向是反的。把方向掉过来，一切就顺了：从右往左扫，遇到的
#一定作用于它左边的字符，也就是尚未访问到的部分。于是只要拿一个整数skip记账——见到一个#就skip++，见到普通字符时若skip > 0就skip--并把它跳过，否则这个字符就是「最终文本从右往左数的下一个有效字符」。整数计数替代了栈，空间降到 $O(1)$。另一个关键观察是：不需要先归约完再整体比较，可以边归约边比较。两个串各自维护一对
(下标, skip)，每轮各自向左推进到下一个有效字符，然后当场比对这两个字符。这正是「从后往前」的另一个好处——最终文本的对齐是从右端开始的，右端对齐不需要预先知道长度。不变量：每一轮外层循环开始前，
s[i+1..]与t[j+1..]归约后的文本已经逐字符比对通过且完全相同；内层跳过循环结束后，i要么小于 0（该串的有效字符已用尽），要么指向s归约文本中当前待比较的最右字符，t与j同理。当一边耗尽而另一边还有有效字符时，用一个哨兵值（
0或\0）代表「没有字符」，它与任何真实字符都不相等，于是长度不等的情况被自然判否，不需要单独写分支。外层循环用i >= 0 || j >= 0（而非&&）正是为了让这种不平衡的情况也能进入循环并被判否。
解题步骤
- 初始化：
i = s.length() - 1、j = t.length() - 1、skipS = skipT = 0。从末尾起步，因为退格的作用方向是向左，只有逆序扫描才能在遇到#时立刻知道它要删谁。- 外层循环条件
i >= 0 || j >= 0：用「或」而不是「且」。若写成「且」，"a"与""会一次循环都不进而直接返回 true，长度不等的错误就漏掉了。- 内层推进
i：只要i >= 0就循环：字符是#则skipS++, i--；否则若skipS > 0则skipS--, i--（这个字符被删掉了）；否则break，此时i指向一个真正有效的字符。三个分支的顺序不能换——必须先判#，因为#本身也要在有欠账时继续累积，而不是被当作被删对象。- 内层推进
j：与上一步对称，两个串各自记账、互不干扰。- 取字符并比较：
a = i >= 0 ? s.charAt(i) : 0，b同理。用0作哨兵是因为题目保证字符是小写字母，\0不可能出现在输入里，这样「一方没了另一方还有」必然不相等。若a != b立即返回 false。- 同时后退一格：
i--、j--，把刚比较过的这对有效字符消费掉，进入下一轮。- 循环正常结束返回 true：能走到这里说明每一对有效字符都相等且同时耗尽。
以
s = "ab#c"、t = "ad#c"走一遍（两者归约后都是"ac"）。初始
i = 3、j = 3、skipS = skipT = 0。第 1 轮：
s[3] = 'c'不是#且skipS = 0，立刻break，i停在 3；t[3] = 'c'同理，j停在 3。取a = 'c'、b = 'c'，相等。i--得 2，j--得 2。第 2 轮：
s[2] = '#'，skipS升为 1，i退到 1；s[1] = 'b'不是#但skipS = 1 > 0，于是skipS归零、i退到 0（b被退格删掉了）；s[0] = 'a'是有效字符，break。t侧完全对称：#让skipT变 1，d被删，j停在 0。取a = 'a'、b = 'a'，相等。i--得 -1，j--得 -1。第 3 轮：
i < 0且j < 0，外层条件不成立，循环退出，返回 true。再看一个不等的用例
s = "a#c"、t = "b"。第 1 轮i = 2指向'c'直接有效，j = 0指向'b'直接有效，'c' != 'b'，立即返回 false。若把外层条件误写成&&，在s = "a#c"、t = ""这种一方为空的输入上会直接返回 true，而正确答案是 false——这就是「或」的必要性。
代码实现
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = s.length() - 1;
int j = t.length() - 1;
int skipS = 0;
int skipT = 0;
while (i >= 0 || j >= 0) {
while (i >= 0) {
char c = s.charAt(i);
if (c == '#') {
skipS++;
i--;
} else if (skipS > 0) {
skipS--;
i--;
} else {
break;
}
}
while (j >= 0) {
char c = t.charAt(j);
if (c == '#') {
skipT++;
j--;
} else if (skipT > 0) {
skipT--;
j--;
} else {
break;
}
}
char a = i >= 0 ? s.charAt(i) : 0;
char b = j >= 0 ? t.charAt(j) : 0;
if (a != b) {
return false;
}
i--;
j--;
}
return true;
}
}
func backspaceCompare(s string, t string) bool {
i, j := len(s)-1, len(t)-1
skipS, skipT := 0, 0
for i >= 0 || j >= 0 {
for i >= 0 {
if s[i] == '#' {
skipS++
i--
} else if skipS > 0 {
skipS--
i--
} else {
break
}
}
for j >= 0 {
if t[j] == '#' {
skipT++
j--
} else if skipT > 0 {
skipT--
j--
} else {
break
}
}
var a byte = 0
var b byte = 0
if i >= 0 {
a = s[i]
}
if j >= 0 {
b = t[j]
}
if a != b {
return false
}
i--
j--
}
return true
}
复杂度分析
- 时间复杂度：$O(n + m)$。
i与j各自只单调左移，全程不回头，每个字符最多被访问一次；外层循环虽然嵌套了内层，但内层推进的是同一对指针，不会重复扫描。- 空间复杂度：$O(1)$。只用了两个下标、两个退格计数和两个临时字符，与串长无关。这正是本题进阶要求的答案，也是它优于栈解法的唯一理由。
关键点总结
- 当某种操作的影响方向朝左（退格、覆盖、抵消），从右往左扫往往能把「必须缓存」变成「用计数记账」，这是把 $O(n)$ 空间降到 $O(1)$ 的通用手法。
- 用一个不可能出现在输入里的哨兵值代表「已耗尽」，可以把长度不等的分支融进主比较逻辑，少写一段容易错的特判。
- 双指针的终止条件要覆盖「一方先耗尽」的情形；此题用「或」而非「且」就是这个道理，写成「且」会静默放过一整类错误。
- 内层跳过循环里三个分支的判断顺序（先
#、再有欠账、最后有效字符）承载了「退格可累积」的语义，顺序一换语义就变了。- 面试视角：先给栈解法证明思路正确，再主动提出「进阶要求 $O(1)$ 空间」并给出逆序双指针，是这题的满分答法；只写栈会被追问，只写双指针则难以说明推导过程。
- 归约后的两个文本从右端对齐比较，比从左端对齐省去了「先算最终长度」的一步——选对齐方向本身就是一种优化。
易错点总结
- 外层条件写成
i >= 0 && j >= 0：s = "a"、t = ""直接不进循环返回 true，正确答案是 false。所有「一方先耗尽」的用例都会被漏判。- 内层先判
skip > 0再判#：s = "ab##"中处理到第二个#时会因为skipS已为 1 而把它当作被删字符消耗掉，skipS归零，最终归约成"a"而不是空串。skip用布尔而不是计数："abc###"需要连续删三个字符，布尔只能记住「有一次退格」，结果得到"ab"而不是空串。- 退格数在空文本上「欠账」：若写成
skipS--后不检查有效字符是否存在就继续，"###a"会把a也删掉返回空串，正确结果是"a"。本实现靠「只有遇到非#字符才消耗skip」天然避免了这个问题。- 取字符时忘记下标为负的保护：
s = "a#"、t = "b"中i会被推到 -1，直接s.charAt(i)抛越界异常。- 哨兵取成
' '或'a'：若哨兵是可能出现的字符，s = ""、t = "a"会把「没有字符」误判成等于'a'而返回 true。- 比较后只后退一个指针：写完
i--忘了j--，s = "ab"、t = "ab"会让j原地不动，反复拿t的同一个字符比较，最终越界或死循环。- 用栈解法时弹栈前不判空：
"#a"的第一个#对空栈执行pop()会抛异常；题目明确规定对空文本退格是无操作。- 把
#理解成删除右边的字符："a#b"会被算成"ab"去掉b即"a"（巧合正确），但"#ab"会被算成"b"而正确答案是"ab"，方向理解错在含前导退格的用例上暴露。- 两个串的
skip共用一个变量：s = "a#b"、t = "cd"中s累积的退格会错误地作用到t上，把t的字符跳掉，得出两串相等的错误结论。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 2390. 从字符串中移除星号 | 中等 | 同为「删除左侧一个字符」，但只需构造结果串，不必两串比对 |
| 1047. 删除字符串中的所有相邻重复项 | 简单 | 抵消条件由「遇到特定符号」变成「与栈顶相同」，逆序技巧不再适用 |
| 71. 简化路径 | 中等 |
.. 是分段级别的退格，需先按 / 切分再用栈，无法用单个计数替代 |
| 20. 有效的括号 | 简单 | 抵消的是括号类型，必须记住栈里的具体符号，$O(1)$ 空间做不到 |
| 392. 判断子序列 | 简单 | 同为双串双指针，但两指针推进条件不对称，只在匹配时才推进短串 |
| 26. 删除有序数组中的重复项 | 简单 | 快慢指针原地覆写，写指针只在保留元素时前进，也是 $O(1)$ 空间 |
| 443. 压缩字符串 | 中等 | 原地读写双指针，额外要处理多位数字回写导致的写指针跳跃 |
| 925. 长按键入 | 简单 | 双串双指针比对，规则是「允许目标串重复」而非「删除」 |