[数据结构与算法]leetcode 844 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。

如果相等，返回 true ；否则，返回 false 。

注意：如果对空文本输入退格字符，文本继续为空。

示例 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 = “#a#c”
输出：true
解释：s 和 t 都会变成 “c”。
示例 4：

输入：s = “a#c”, t = “b”
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。

用栈重构
最容易想到的方法是将给定的字符串中的退格符和应当被删除的字符都去除，还原给定字符串的一般形式。然后直接比较两字符串是否相等即可。具体地，我们用栈处理遍历过程，每次我们遍历到一个字符：
如果它是退格符，那么我们将栈顶弹出；
如果它是普通字符，那么我们将其压入栈中。
时间复杂度O(m+n)
空间复杂度O(m+n)

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        return self.build(s) == self.build(t)
    
    def build(self, s):
        stack = ''
        for elem in s:
            if elem != '#':
                stack += elem
            else:
                if len(stack) > 0:
                    stack = stack[:-1]
        return stack

双指针
一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。具体地，我们定义两个指针，分别指向两字符串的末尾。我们定义 两个skip 表示对应字符串当前待删除的字符的数量, 都初始为0。只要有一个双指针没遍历完，就继续逆序遍历字符（初始状态如果一个字符串为空，一个不为空，直接返回true是不对的，所以只要有一个字符串没遍历完就要继续遍历）：
1
若该字符为退格符，则我们需要多删除一个普通字符，我们让 skip 加 1，对应指针继续逆序移动1格；

若该字符为普通字符：
若 skip=0，则说明当前字符不需要删去，需要用这个字符串参与比较；
若 skip>0，则说明当前字符需要删去，我们让skip减 1，指针也要继续逆序移动一格。

2
两个指针都没有遍历完（指针为-1），此时他们都指向一个不需要删除的字符，将这两个字符进行比较，如果不相等则直接返回false

如果其中一个先遍历完，另一个还没有（也就是指向一个不需要删除的字符），也返回FALSE

如果全部都遍历结束了，则返回True

3
如果还没有返回，则两个指针同时-1，继续遍历

空间复杂度O(1)

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i = len(s) - 1 
        j = len(t) - 1 
        skipi = 0
        skipj = 0
        while (i >= 0) or (j >= 0):
            while i >= 0:
                if (s[i] == '#'):
                    skipi += 1
                    i -= 1
                elif skipi > 0:
                    skipi -= 1
                    i -= 1
                else:
                    break
            
            while j >= 0:
                if (t[j] == '#'):
                    skipj += 1 
                    j -= 1 
                elif skipj > 0:
                    skipj -= 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 -= 1 
            j -= 1 
        return True