844-比较含退格的字符串.md

844-比较含退格的字符串

原题

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

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

输入：s = "ab#c", t = "ad#c" 输出：true 解释：s 和 t 都会变成 "ac"。

输入：s = "ab##", t = "c#d#" 输出：true 解释：s 和 t 都会变成 ""。

用双指针的方式是最合理的方式

const backspaceStringCompare = function (s, t) {
  let i = s.length - 1;
  let j = t.length - 1;
  let n = 0; // s 字符串含有 # 的个数（不是总的个数，是计算时做一个临时统计）
  let m = 0; // t 字符串含有 # 的个数
  while (i >= 0 || j >= 0) {
    while (i >= 0) {
      if (s[i] === '#') {
        n++;
        i--;
      } else if (n > 0) {
        n--;
        i--;
      } else {
        break;
      }
    }

    while (j >= 0) {
      if (t[j] === '#') {
        m++;
        j--;
      } else if (m > 0) {
        m--;
        j--;
      } else {
        break;
      }
    }

    if (s[i] !== t[j]) {
      return false;
    }

    i--;
    j--;
  }

  return true;
};

let s = 'ab#c',
  t = 'adc##c';
let result = backspaceStringCompare(s, t);