0844. 比较含退格的字符串

0844. 比较含退格的字符串 #

  • 标签:栈、双指针、字符串、模拟
  • 难度:简单

题目大意 #

给定 st 两个字符串。字符串中的 # 代表退格字符。

要求:当它们分别被输入到空白的文本编辑器后,判断二者是否相等。如果相等,返回 True;否则,返回 False

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

解题思路 #

这道题的第一个思路是用栈,第二个思路是使用分离双指针。

思路一:栈。

  • 定义一个构建方法,用来将含有退格字符串构建为删除退格的字符串。构建方法如下。
    • 使用一个栈存放删除退格的字符串。
    • 遍历字符串,如果遇到的字符不是 #,则将其插入到栈中。
    • 如果遇到的字符是 #,且当前栈不为空,则将当前栈顶元素弹出。
  • 分别使用构建方法处理字符串 st,如果处理完的字符串 st 相等,则返回 True,否则返回 False

思路二:分离双指针。

由于 # 会消除左侧字符,而不会影响右侧字符,所以我们选择从字符串尾端遍历 st 字符串。具体做法如下:

  • 使用分离双指针 left_1left_2left_1 指向字符串 s 末尾,left_2 指向字符串 t 末尾。使用 sign_1sign_2 标记字符串 st 中当前退格字符个数。
  • 从后到前遍历字符串 st
    • 先来循环处理字符串 s 尾端 # 的影响,具体如下:
      • 如果当前字符是 #,则更新 s 当前退格字符个数,即 sign_1 += 1。同时将 left_1 左移。
      • 如果 s 当前退格字符个数大于 0,则退格数减一,即 sign_1 -= 1。同时将 left_1 左移。
      • 如果 s 当前为普通字符,则跳出循环。
    • 同理再来处理字符串 t 尾端 # 的影响,具体如下:
      • 如果当前字符是 #,则更新 t 当前退格字符个数,即 sign_2 += 1。同时将 left_2 左移。
      • 如果 t 当前退格字符个数大于 0,则退格数减一,即 sign_2 -= 1。同时将 left_2 左移。
      • 如果 t 当前为普通字符,则跳出循环。
    • 处理完,如果两个字符串为空,则说明匹配,直接返回 True
    • 再先排除长度不匹配的情况,直接返回 False
    • 最后判断 s[left_1] 是否等于 s[left_2]。不等于则直接返回 False,等于则令 left_1left_2 左移,继续遍历。
  • 遍历完没有出现不匹配的情况,则返回 True

代码 #

  • 思路一:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def build(self, s: str):
        stack = []
        for ch in s:
            if ch != '#':
                stack.append(ch)
            elif stack:
                stack.pop()
        return stack
        
    def backspaceCompare(self, s: str, t: str) -> bool:
        return self.build(s) == self.build(t)
  • 思路二:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        left_1, left_2 = len(s) - 1, len(t) - 1
        sign_1, sign_2 = 0, 0
        while left_1 >= 0 or left_2 >= 0:
            while left_1 >= 0:
                if s[left_1] == '#':
                    sign_1 += 1
                    left_1 -= 1
                elif sign_1 > 0:
                    sign_1 -= 1
                    left_1 -= 1
                else:
                    break

            while left_2 >= 0:
                if t[left_2] == '#':
                    sign_2 += 1
                    left_2 -= 1
                elif sign_2 > 0:
                    sign_2 -= 1
                    left_2 -= 1
                else:
                    break

            if left_1 < 0 and left_2 < 0:
                return True
            if left_1 >= 0 and left_2 < 0:
                return False
            if left_1 < 0 and left_2 >= 0:
                return False
            if s[left_1] != t[left_2]:
                return False

            left_1 -= 1
            left_2 -= 1

        return True
本站总访问量  次  |  您是本站第  位访问者