难度: Easy
给定 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) 的空间复杂度解决该问题吗？运行时间: 16 ms
内存: 16.0 MB
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
ret=list()
ret2=list()
for i in range(len(s)):
if s[i]!='#':
ret.append(s[i])
elif ret:
ret.pop()
for j in range(len(t)):
if t[j]!='#':
ret2.append(t[j])
elif ret2:
ret2.pop()
# ret="".join(ret)
# ret2="".join(ret2)
return ret==ret2
该题解采用的思路是使用栈来模拟退格操作。对于两个字符串s和t，分别使用一个栈来处理每个字符串中的字符。遍历字符串中的每个字符，如果不是'#'，则将字符推入栈中；如果是'#'，则从栈中弹出一个字符（如果栈不为空）。遍历完成后，栈中剩余的字符序列即为处理退格后的结果。最后，比较两个栈的内容是否相同，以确定两个字符串处理退格后是否相等。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
# 初始化两个栈来处理s和t
ret=list()
ret2=list()
# 处理字符串s
for i in range(len(s)):
if s[i] != '#':
ret.append(s[i]) # 如果字符不是'#'，则添加到栈中
elif ret:
ret.pop() # 如果栈不为空且当前字符是'#'，则弹出栈顶元素
# 处理字符串t
for j in range(len(t)):
if t[j] != '#':
ret2.append(t[j]) # 如果字符不是'#'，则添加到栈中
elif ret2:
ret2.pop() # 如果栈不为空且当前字符是'#'，则弹出栈顶元素
# 比较两个栈的内容是否相同
return ret == ret2
栈是一种后进先出（LIFO）的数据结构，非常适合处理与顺序相关的逆向操作问题。在处理退格符'#'的场景中，当遇到一个字符时，我们希望将其加入序列；而当遇到'#'时，我们需要删除最近加入的字符。这种“最后一个进入，首先被删除”的特性正是栈的操作特点，因此使用栈来模拟这一过程可以简洁且直观地实现退格操作的正确逻辑。
在算法中，每次遇到'#'字符时，会检查栈是否为空。如果栈不为空，则弹出栈顶元素，即删除最近一个非退格字符。如果栈为空，则忽略这个退格操作。因此，即使连续遇到多个'#'字符，算法也会按照每个'#'依次处理，每次要么删除栈顶字符（如果存在），要么什么也不做（如果栈已空），这样就能保证正确处理连续退格的情况。
当前的解决方案没有在遍历过程中直接进行比较，而是分别处理完两个字符串后，再比较两个栈的内容。这种方法虽然简单，但确实存在性能优化的空间。例如，可以在构建栈的同时记录栈的长度，如果在任何时点两个栈的长度不同，则可以直接判定两个字符串处理后不相等，从而提前结束程序。另外，如果允许在两个字符串上直接操作，还可以采用双指针技术从后向前遍历，边遍历边比较，这样可以进一步减少空间复杂度，提高算法效率。
在当前算法设计中，如果字符串以退格符'#'开始，该算法仍然能够正确处理。这是因为算法在遇到每一个'#'字符时都会先检查栈是否为空。如果栈为空（如在字符串开始就遭遇'#'），则不执行任何操作，即忽略这些退格。这样的逻辑确保了即使字符串以一个或多个'#'开始，算法依然能够正确执行，不需要额外的特殊处理。