【力扣】844. 比较含退格的字符串

给定 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 <= 200
• s 和 t 只含有小写字母以及字符 '#'

进阶：

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

题解：

常规（支持Unicode字符）：

// 时间复杂度：O(n+m)，n 和 m 分别为 s 和 t 的长度
// 空间复杂度：O(n+m)，n 和 m 分别为 s 和 t 的长度
func backspaceCompare(s string, t string) bool {
	// 创建了一个闭包函数
	processText := func(s string) string {
		backspaceCount := 0
		// 字符串转成 rune 类型
		runes := []rune(s)
		// 从右开始遍历整个字符串
		for i := len(s) - 1; i >= 0; i-- {
			if runes[i] == '#' {
				// 遇到 # 号了，统计数量，并删除字符（# 号）
				backspaceCount++
				runes[i] = 0
			} else if backspaceCount > 0 {
				// 这里是需要删除字符，同时 # 号的统计数量开始减少
				backspaceCount--
				runes[i] = 0
			}
		}
		// 闭包函数返回字符串
		return string(runes)
	}
	return processText(s) == processText(t)
}

栈（支持Unicode字符）：

// 时间复杂度：O(n+m)，n 和 m 分别为 s 和 t 的长度
// 空间复杂度：O(n+m)，n 和 m 分别为 s 和 t 的长度
func backspaceCompare(s, t string) bool {
	processText := func(str string) string {
		var b []rune
		for _, char := range str {
			if char != '#' {
				b = append(b, char)
			} else if len(b) > 0 {
				b = b[:len(b)-1]
			}
		}
		return string(b)
	}
	return processText(s) == processText(t)
}

双指针法：

// 时间复杂度：O(n)
// 空间复杂度：O(1)
func backspaceCompare(s, t string) bool {
	skipS, skipT := 0, 0
	// 从字符串的末尾开始比较
	i, j := len(s)-1, len(t)-1
	for i >= 0 || j >= 0 {
		// 对字符串 s 进行遍历和处理
		for i >= 0 {
			if s[i] == '#' {
				// 遇到 '#', 记录需要跳过的字符数量，并向前移动指针
				skipS++
				i--
			} else if skipS > 0 {
				// 有需要跳过的字符，向前移动指针，并减少需要跳过的字符数量
				skipS--
				i--
			} else {
				// 没有需要跳过的字符，结束遍历
				break
			}
		}
		// 对字符串 t 进行遍历和处理，处理方式和对 s 的处理一样
		for j >= 0 {
			if t[j] == '#' {
				skipT++
				j--
			} else if skipT > 0 {
				skipT--
				j--
			} else {
				break
			}
		}

		// 如果 i 和 j 都有效（都指向了一个真实的字符），比较他们对应的字符
		if i >= 0 && j >= 0 {
			if s[i] != t[j] {
				return false
			}
		} else if i >= 0 || j >= 0 {
			// 处理 s 和 t 字符串长度不一致的情况
			// 如果 i 或 j 其中一个还指向一个实际字符，另外一个没字符了，则返回 false
			return false
		}
		// 向前移动 i 和 j，开始处理下一对字符
		i--
		j--
	}
	return true
}