比较含退格的字符串

记住「从右往左 + skip 计数,找有效字符两两比」。为什么从右往左?因为退格只影响它左边的字符,从右扫才能当场算清谁被删。

先看 s。指针从最右第 7 位起步,带一个 skip=0。下面一格一格往左走,边走边算哪些字符真正留下来。

t 也一样,指针落在最右第 7 位、skip=0。两个串各自找「下一个有效字符」,再把这一对拿来比。

s 的第 7 位是 "e",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。s 当前化简成 "e"。

t 的第 7 位是 "e",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。t 当前化简成 "e"。

把这一对有效字符摆出来比:s 是 "e"、t 是 "e"。一样,接着找下一对。

s 的第 6 位是 "d",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。s 当前化简成 "de"。

t 的第 6 位是 "d",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。t 当前化简成 "de"。

把这一对有效字符摆出来比:s 是 "d"、t 是 "d"。一样,接着找下一对。

s 的第 5 位是退格键 #,欠一次删除,skip 加到 1。# 本身不是字符,继续往左。

s 的第 4 位是 "c",可前面还欠着退格(skip 从 1 减到 0),所以它被删掉、灰掉跳过。

s 的第 3 位是退格键 #,欠一次删除,skip 加到 1。# 本身不是字符,继续往左。

s 的第 2 位是 "b",可前面还欠着退格(skip 从 1 减到 0),所以它被删掉、灰掉跳过。

s 的第 1 位是 "a",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。s 当前化简成 "ade"。

t 的第 5 位是退格键 #,欠一次删除,skip 加到 1。# 本身不是字符,继续往左。

t 的第 4 位是退格键 #,欠一次删除,skip 加到 2。# 本身不是字符,继续往左。

t 的第 3 位是 "z",可前面还欠着退格(skip 从 2 减到 1),所以它被删掉、灰掉跳过。

t 的第 2 位是 "b",可前面还欠着退格(skip 从 1 减到 0),所以它被删掉、灰掉跳过。

t 的第 1 位是 "a",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。t 当前化简成 "ade"。

把这一对有效字符摆出来比:s 是 "a"、t 是 "a"。一样,接着找下一对。

s 的第 0 位是 "x",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。s 当前化简成 "xade"。

t 的第 0 位是 "x",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。t 当前化简成 "xade"。

把这一对有效字符摆出来比:s 是 "x"、t 是 "x"。一样,接着找下一对。

两个串从右扫到头,逐对有效字符全都对得上,s 化简成 "xade"、t 化简成 "xade",完全一样,返回 true。全程只用了两个指针和两个 skip 计数,没有另开字符串,空间 O(1)。

边界:开头多余的 # 自动作废、删空后是空串、两个空串相等。

两个高频追问:栈解法(O(n) 空间)对比双指针(O(1) 空间),以及为什么双指针省空间。