「每日LeetCode」2020年10月19日

本文最后更新于：2023年3月19日 晚上

Lt844. 比较含退格的字符串、双指针

844. 比较含退格的字符串

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
 示例 1：

1
2
3
输入：S = "ab#c", T = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。

示例 2：

1
2
3
输入：S = "ab##", T = "c#d#"
输出：true
解释：S 和 T 都会变成 “”。

示例 3：

1
2
3
输入：S = "a##c", T = "#a#c"
输出：true
解释：S 和 T 都会变成 “c”。

示例 4：

1
2
3
输入：S = "a#c", T = "b"
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。

提示：

  1. 1 <= S.length <= 200
  2. 1 <= T.length <= 200
  3. S 和 T 只含有小写字母以及字符 '#'。

进阶：

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

思路

栈储存结果

时间复杂度、空间复杂度都为 O(n)。使用一个 isDelete 计数退格符的数量，遍历字符串每一个字符，如果是退格符则计数加一跳过当前循环，如果非退格符且 isDelete 计数大于 0 则计数减一，跳过当前循环，相当于删除当前字符

双指针

使用两个指针分别指向两个字符串尾部，当两个指针其中一个还指向有效位数前，进行循环：

  1. 对 S 进行循环，如果是退格符，skip1 计数加一，l1–；如果非退格符但 skip1>0，说明是需要删除的字符，skip1–，l1–；如果非退格符，且 skip1===0，说明是需要判断的字符串，退出循环。
  2. 对 T 进行同上循环。
  3. 如果两个指针都是有效下标，则判断两个指针指向的字符是否相等，不相等则返回 false；如果其中一个是无效下标，即该字符串已退格完毕，如果另外一个字符串的下标仍大于等于 0，说明还存在字符串未退格，两个字符串的长度不相等，返回 false；
  4. 如果字符串相等的且下标有效的情况下，判断以后另两个指针都减一，判断下一个字符

解答

栈储存结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {string} S
 * @param {string} T
 * @return {boolean}
 */
var backspaceCompare = function (S, T) {
  const compare = (s) => {
    const res = [];
    let isDelete = 0;
    for (let i = s.length - 1; i >= 0; i--) {
      const arr = s[i];
      if (arr === "#") {
        isDelete++;
        continue;
      }
      if (arr !== "#" && isDelete > 0) {
        isDelete--;
        continue;
      }
      res.unshift(arr);
    }
    return res.join("");
  };
  return compare(S) === compare(T);
};

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * @param {string} S
 * @param {string} T
 * @return {boolean}
 */
var backspaceCompare = function (S, T) {
  let l1 = S.length - 1,
    l2 = T.length - 1;
  let skip1 = 0,
    skip2 = 0;
  while (l1 >= 0 || l2 >= 0) {
    while (l1 >= 0) {
      if (S[l1] === "#") {
        skip1++;
        l1--;
      } else if (skip1 > 0) {
        skip1--;
        l1--;
      } else {
        break;
      }
    }
    while (l2 >= 0) {
      if (T[l2] === "#") {
        skip2++;
        l2--;
      } else if (skip2 > 0) {
        skip2--;
        l2--;
      } else {
        break;
      }
    }
    if (l1 >= 0 && l2 >= 0) {
      if (S[l1] !== T[l2]) {
        return false;
      }
    } else {
      if (l1 >= 0 || l2 >= 0) {
        return false;
      }
    }
    l1--;
    l2--;
  }
  return true;
};