LeetCode 题解工作台
比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。 # 代表退格字符。 注意： 如果对空文本输入退格字符，文本继续为空。 示例 1： 输入： s = "ab#c", t = "ad#c" 输出： true 解释： s 和 t 都会变成 "ac"。 示…
4
题型
6
代码语言
3
相关题
当前训练重点
简单 · 双·指针·invariant
答案摘要
我们用双指针 和 分别指向字符串 和 的末尾。 每次向前移动一个字符，如果当前字符是退格符，则跳过当前字符，同时退格符的数量加一，如果当前字符不是退格符，则判断退格符的数量，如果退格符的数量大于 ，则跳过当前字符，同时退格符的数量减一，如果退格符的数量等于 ，那么该字符需要进行比较。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = "ab#c", t = "ad#c" 输出：true 解释：s 和 t 都会变成 "ac"。
示例 2：
输入：s = "ab##", t = "c#d#" 输出：true 解释：s 和 t 都会变成 ""。
示例 3：
输入：s = "a#c", t = "b" 输出：false 解释：s 会变成 "c"，但 t 仍然是 "b"。
提示：
1 <= s.length, t.length <= 200s和t只含有小写字母以及字符'#'
进阶：
- 你可以用
O(n)的时间复杂度和O(1)的空间复杂度解决该问题吗？
解题思路
方法一：双指针
我们用双指针 和 分别指向字符串 和 的末尾。
每次向前移动一个字符，如果当前字符是退格符，则跳过当前字符，同时退格符的数量加一，如果当前字符不是退格符，则判断退格符的数量，如果退格符的数量大于 ，则跳过当前字符，同时退格符的数量减一，如果退格符的数量等于 ，那么该字符需要进行比较。
我们每次找到两个字符串中需要比较的字符，然后进行比较，如果两个字符不相等，则返回 ，如果遍历完两个字符串，都没有发现不相等的字符，则返回 。
时间复杂度 ，空间复杂度 。其中 和 分别是字符串 和 的长度。
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
i, j, skip1, skip2 = len(s) - 1, len(t) - 1, 0, 0
while i >= 0 or j >= 0:
while i >= 0:
if s[i] == '#':
skip1 += 1
i -= 1
elif skip1:
skip1 -= 1
i -= 1
else:
break
while j >= 0:
if t[j] == '#':
skip2 += 1
j -= 1
elif skip2:
skip2 -= 1
j -= 1
else:
break
if i >= 0 and j >= 0:
if s[i] != t[j]:
return False
elif i >= 0 or j >= 0:
return False
i, j = i - 1, j - 1
return True
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(M + N) since each character in s and t is processed at most once. Space complexity is O(1) because only counters and pointers are used without additional storage. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Check if you can handle consecutive backspaces correctly when pointers cross multiple '#' characters.
- question_mark
Notice if the candidate compares characters without correctly skipping invalid ones.
- question_mark
Watch if they optimize space by avoiding auxiliary stacks or rebuilt strings.
常见陷阱
外企场景- error
Failing to skip multiple consecutive backspaces properly leading to incorrect character comparisons.
- error
Attempting to build processed strings instead of scanning with two pointers, increasing unnecessary space usage.
- error
Not handling cases where one string is exhausted while the other still has pending backspaces.
进阶变体
外企场景- arrow_right_alt
Compare strings with different special characters representing backspaces or deletions.
- arrow_right_alt
Compute equality when backspaces are applied from the start instead of scanning backward.
- arrow_right_alt
Determine if one string can be transformed into the other using a limited number of backspaces.