844. 比较含退格的字符串

🎯 问题描述

描述：
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。

说明：

这是一个典型的栈应用问题。
核心策略：
- 我们需要模拟字符串的输入过程。
- 遇到普通字符时，将其“输入”（入栈）。
- 遇到 # 字符时，执行“退格”（出栈），前提是栈不为空。
- 最后比较两个字符串处理后的结果。
示例：
示例 1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：
- s 变为 "ac" ('b' 被退格删除)
- t 变为 "ac" ('d' 被退格删除)
- 两者相等。

示例 2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：
- s 变为 "" ('b' 被删除，然后 'a' 被删除)
- t 变为 "" ('d' 被删除，然后 'c' 被删除)
- 两者相等。

💻 解题思路

思路1：栈模拟

核心逻辑

定义处理函数 Modle：
- 创建一个空栈 stack。
- 遍历输入字符串 st 的每个字符 s。
- 判断字符类型：
  - 如果是 #：执行退格操作。如果栈不为空，弹出栈顶元素（stack.pop()）。
  - 如果是普通字符：执行输入操作，将字符压入栈（stack.append(s)）。
- 遍历结束后，将栈中剩余字符拼接成字符串返回。
比较结果：
- 分别对 s 和 t 调用 Modle 函数，得到处理后的字符串 p1 和 p2。
- 返回 p1 == p2。

代码实现

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        # 定义一个辅助函数来处理含退格符的字符串
        def Modle(st: str):
            stack = []
            for char in st:  
                if char == "#":
                    # 如果是退格符，且栈不为空，则弹出栈顶元素
                    if stack:
                        stack.pop()
                else:
                    # 如果是普通字符，压入栈
                    stack.append(char)
            # 将栈中字符拼接成最终字符串
            return "".join(stack)
        
        # 分别处理两个字符串
        p1 = Modle(s)
        p2 = Modle(t)
        
        # 比较结果
        return p1 == p2

📊 性能分析

时间复杂度： $O(N + M)$ $O (N + M)$
- 其中 $N$ 和 $M$ 分别是字符串 s 和 t 的长度。
- 我们需要遍历两个字符串各一次，每次操作（入栈、出栈）都是 $O(1)$ 。
空间复杂度： $O(N + M)$ $O (N + M)$
- 我们需要两个栈来存储处理后的字符。
- 在最坏情况下（没有退格符），栈的大小等于字符串长度。

思考

为什么使用栈？
- 退格操作的本质是“撤销最近一次输入”。
- 这种“后进先出”（LIFO）的操作模式正是栈的核心特性。
边界情况处理：
- 代码中 if stack: 的判断非常重要。
- 如果栈为空时遇到 #，不做任何操作，这符合题目“对空文本输入退格字符，文本继续为空”的要求。