LeetCode 844. 比较含退格的字符串

题目

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

方法一：栈

栈即只能在一端进行插入和删除操作。所以此题可以使用栈的思路。

class Solution(object):
    def get_string(self, n):
        stack = []
        for i in range(len(n)):
            if n[i] != "#":
                stack.append(n[i])
            elif len(stack) > 0:
                stack.pop()
        return str(stack)

    def backspaceCompare(self, s, t):
        return self.get_string(s) == self.get_string(t)

方法二：双指针

思路：
一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。

设 skipS 和 skipT 为 # 字符的个数。
循环字符串 s 和 t，并且再通过内部的循环来从后向前寻找有意义的字母，并进行比较。
在内部循环中，需要对此次的字符进行判断：

• 若为 #， 则skipS + 1并继续循环；
• 若此时skipS > 0，表示此时还有 # 未发挥作用，即此字符不在判断两字符串是否相等的范围内，则skipS - 1并继续循环；
• 直至循环到一个有意义的字符。
  最后一次次判断获取的两个有意义的字符是否相等。

class Solution(object):
    def backspaceCompare(self, s, t):
        i = len(s) - 1
        j = len(t) - 1
        skipS = skipT = 0 

        while i>=0 or j>=0:
            while i >= 0:
                if s[i] == "#":
                    skipS = skipS + 1
                    i = i - 1
                elif skipS > 0:
                    skipS = skipS - 1
                    i = i - 1
                else:
                    break
            while j >= 0:
                if t[j] == "#":
                    skipT = skipT + 1
                    j = j - 1
                elif skipT > 0:
                    skipT = skipT - 1
                    j = 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 = i - 1
            j = j - 1
        return True

相关知识

• append()：
  尾部添加元素
• pop()：
  删除尾部元素

参考

代码相关：https://programmercarl.com/
Leetcode官方解题