目录

0844:比较含退格的字符串(1227 分)

力扣第 87 场周赛第 1 题

题目

给定 st 两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 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 <= 200
  • st 只含有小写字母以及字符 '#'

进阶:

  • 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗?

相似问题:

分析

#1

最简单的就是用栈模拟,然后比较即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def backspaceCompare(self, s: str, t: str) -> bool:
	def help(s):
		stack = []
		for char in s:
			if char != '#':
				stack.append(char)
			elif stack:
				stack.pop()
		return stack
	return help(s) == help(t)

52 ms

#2

题目要求空间复杂度 O(1)。考虑用双指针反向遍历,遇到 ‘#’ 时用 cnt 记录,并跳过相应个数的普通字符,找到下一个有效字符,再进行比较即可。

具体实现时,用辅助函数 nxt(i, s) 表示从当前的有效字符位置 i,反向遍历找到 s 中的下一个有效字符位置。那么初始令 i=len(s), j=len(t), 然后不断调用 nxt(i, s) 和 nxt(j, t) 并比较即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def backspaceCompare(self, s: str, t: str) -> bool:
	def nxt(i, s):
		i, cnt = i-1, 0
		while i >= 0:
			if s[i] != '#' and cnt == 0:
				break
			cnt += 1 if s[i] == '#' else -1
			i -= 1
		return i

	i, j = len(s), len(t)
	while i >= 0 and j >= 0:
		i, j = nxt(i, s), nxt(j, t)
		if not (i >= 0 and j >= 0 and s[i] == t[j] or (i == j == -1)):
			return False
	return True

32 ms