048 · Backspace String Compare

algorithm
Published

June 30, 2026

My First Thoughts

嗯，这道题似乎是上一题的简化版？

上一题 Baseball Game 里有好几种操作：普通分数、"C"、"D"、"+"。这题好像只考虑一种类似 "C" 的情况：遇到 "#"，就删除前面最近的一个字符。

题目要比较两个字符串执行完 "#" 之后是否相同。

那首先需要得到 "#" 处理后的两个字符串，然后直接判断它们是否相等。

要得到处理后的字符串，就需要处理所有的 "#"。

先看 s：

s_clean = ""

for char in s:
    if char != "#":
        s_clean += char
    else:
        s_clean = s_clean[:-1] if s_clean else s_clean

如果当前字符不是 "#"，就把它加到 s_clean 后面。

如果当前字符是 "#"，就删除 s_clean 的最后一个字符。这里还要注意一种情况：如果 s_clean 已经是空字符串，那就没有字符可以删，所以保持原样。

t 也是一样：

t_clean = ""

for char in t:
    if char != "#":
        t_clean += char
    else:
        t_clean = t_clean[:-1] if t_clean else t_clean

最后返回：

return s_clean == t_clean

这个应该就是最先想到的做法。

比如：

s = "ab#c"
t = "ad#c"

s_clean 会从 "a"、"ab"，遇到 "#" 后变回 "a"，最后加上 "c"，得到 "ac"。

t_clean 也会得到 "ac"。

所以返回 True。

到这里看起来已经是正解了，应该没什么额外操作了。

然后我还会想到：能不能提前加一个 len() 判断？如果两个处理后的字符串长度不一样，或许能提前结束，不必字符串逐个比较。

大概思路就是这样。

Why That Is Not Enough

上面的思路是正确的。

它完整模拟了退格过程，也能得到正确答案。真正需要调整的不是算法方向，而是实现方式。

这里的 s_clean += char 和：

s_clean = s_clean[:-1]

都会创建新的字符串。

因为 Python 字符串是不可变的，每次拼接或切片都不是在原字符串上原地修改，而是生成一个新字符串。题目长度只有 200，所以这样写也能通过；但从这题想训练的思路来看，用字符串反复拼接和切片不如用列表自然。

这题和上一题的联系也在这里：我们需要维护“当前还有效的字符”。普通字符加入末尾，"#" 删除末尾。这个行为和上一题里的 append / pop 很像。

至于 len() 提前判断，也不是很必要。

因为必须先把两个字符串都处理完，才知道它们最终长度是多少。处理完以后，直接：

return s_clean == t_clean

就足够了。Python 比较字符串时本身会处理长度不同的情况，不需要额外手写一次长度判断。

Final Idea

保留原来的整体思路：

先把每个字符串执行完退格，得到最终字符串，再比较两个最终字符串。

只是把 s_clean 从字符串改成列表。

也就是不用：

s_clean += char
s_clean = s_clean[:-1]

而是用：

chars.append(char)
chars.pop()

列表的末尾正好代表当前字符串的最后一个有效字符：

  • 遇到普通字符，就加入列表末尾
  • 遇到 "#"，如果列表不空，就删除列表末尾
  • 遍历结束后，把列表用 "".join(chars) 变回字符串

因为 s 和 t 都要做同样的处理，所以可以写一个辅助函数 build。

build(text) 的意思是：

返回 text 执行完所有退格以后的最终字符串。

然后主函数只要比较：

build(s) == build(t)

Why It Works

对任意一个字符串来说，最终结果只取决于从左到右执行每个字符的效果。

当遇到普通字符时，它会留在最终文本里，除非后面被 "#" 删除。所以可以先把它加入当前有效字符列表：

chars.append(char)

当遇到 "#" 时，它会删除前一个还没有被删除的字符。这个字符正好是 chars 的最后一个元素，所以可以用：

chars.pop()

如果 chars 已经为空，说明前面没有字符可以删，这个 "#" 就不产生任何效果。

遍历结束后，chars 里保存的就是所有仍然有效的字符，并且顺序没有变。把它们拼回字符串，就是这个输入执行完退格后的结果。

分别算出 s 和 t 的最终字符串，再比较它们是否相等，就能得到题目要求的答案。

Code

def backspaceCompare(s, t):
    def build(text):
        chars = []

        for char in text:
            if char == "#":
                if chars:
                    chars.pop()
            else:
                chars.append(char)

        return "".join(chars)

    return build(s) == build(t)

Complexity

Time \(O(n + m)\) - n 是 s 的长度，m 是 t 的长度；两个字符串各遍历一次，最后比较结果字符串
Space \(O(n + m)\) - 最坏情况下没有 "#"，需要保存两个字符串的所有字符

Takeaway

当题目要求“删除前一个有效元素”时，可以先想到模拟最终状态。字符串版本可以直接拼接和切片，但更自然的状态通常是列表：普通元素 append，删除操作 pop，最后再把列表转换成需要的结果。

← Quiz