[844] 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。

如果相等，返回 true ；否则，返回 false 。

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

示例 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 = "#a#c"

输出：true

解释：s 和 t 都会变成 “c”。

示例 4：

输入：s = "a#c", t = "b"

输出：false

解释：s 会变成 “c”，但 t 仍然是 “b”。

提示：

1 <= s.length, t.length <= 200

s 和 t 只含有小写字母以及字符 '#'

进阶：

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

比对两字符串经过处理之后是否相等，最容易想到的便是直接处理两字符串，之后在比较相等即可。

我们可以利用遍历 + 栈的方式很容易的实现。

function backspaceCompare(s: string, t: string): boolean {
  return getBackspaceString(s) === getBackspaceString(t);

  function getBackspaceString(str: string): string {
    const res: string[] = [];

    let curr = 0;
    while (curr < str.length) {
      if (str[curr] === '#') {
        if (res.length > 0) res.pop();
      } else {
        res.push(str[curr]);
      }
      curr += 1;
    }

    return res.join('');
  }
}

那么，是否有更好的办法解决呢，答案是肯定的。

这个方法十分巧妙，我们发现，一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此我们只需逆序遍历字符串，则可判断当前字符是否被删除。

可以用两个指针分别指向两字符串的尾部，向前遍历。

遍历过程中的处理原则为：当发现当前字符为#时，退格计数器+1，继续遍历；当前字符不为#时，判断计数器是否清零，若没有则跳过该字符继续遍历。

直到退格计数器为0且当前字符不为#时，才认为真正取到了字符串的最后一个合法字符。

对两个字符串都如此处理后，比对两字符串的最后一个合法字符，若不相等则说明两字符串一定不想等，直接返回false。

直到两个指针都遍历完成，此时如果未发现字符不相等时，返回true。

这样做的时间复杂度为O(N+M)，并且空间复杂度达到了O(1)。

function backspaceCompare(s: string, t: string): boolean {
  let p = s.length - 1;
  let q = t.length - 1;
  let scount = 0;
  let tcount = 0;

  while (p >= 0 || q >= 0) {
    while (p >= 0) {
      if (s[p] === '#') {
        p -= 1;
        scount += 1;
      } else if (scount > 0) {
        p -= 1;
        scount -= 1;
      } else {
        // 只有当欠的退格全部清除后才允许退出
        break;
      }
    }
    while (q >= 0) {
      if (t[q] === '#') {
        q -= 1;
        tcount += 1;
      } else if (tcount > 0) {
        q -= 1;
        tcount -= 1;
      } else {
        // 只有当欠的退格全部清除后才允许退出
        break;
      }
    }
    // 此时字符比对若不同，则字符串一定不同，提前返回
    if (s[p] !== t[q]) return false;

    p -= 1;
    q -= 1;
  }
  return true;
}