题目

力扣题目链接

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

  • 1 <= s.length, t.length <= 200
  • s 和 t 只含有小写字母以及字符 ‘#’

进阶：

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

思路

这种匹配（消除）问题可以用栈或其他数据结构来模拟其过程，最后比较一下即可。

不过，本题可以使用双指针法解决，可在空间复杂度为 O(1) 时解决该问题。

同时从后向前遍历 S 和 T （ i 初始为 S 末尾， j 初始为T末尾），记录 # 的数量，模拟消除的操作，如果 # 用完了，就开始比较 S[i] 和 S[j] 。

动画如下：
1603076585-eXJKxl-844.比较含退格的字符串.gif

答案

Java

双指针，倒序搜索

  1. class Solution {
  2.     public boolean backspaceCompare(String s, String t) {
  3.         int indexA = s.length() - 1, indexB = t.length() - 1;
  4.         char[] charsA = s.toCharArray(), charsB = t.toCharArray();
  6.         // 两者都尚未走到尽头
  7.         while (true) {
  8.             indexA = nextIndex(charsA, indexA);
  9.             indexB = nextIndex(charsB, indexB);
  11.             // 如果两个字符串其中有任意一个已遍历完成
  12.             if (indexA < 0 || indexB < 0) {
  13.                 // 退出循环
  14.                 break;
  15.             }
  17.             // 当前寻找到的两个有效字符不相等
  18.             if (charsA[indexA] != charsB[indexB]) {
  19.                 // 即字符串 s 与 t 不相等
  20.                 return false;
  21.             }
  23.             // 寻找下一个有效字符进行比对
  24.             indexA--;
  25.             indexB--;
  26.         }
  28.         // 两个字符串其中有任意一个已遍历完成, 且都不存在有效字符
  29.         if (indexA == -1 && indexB == -1) {
  30.             // 即字符串 s 与 t 相等
  31.             return true;
  32.         }
  34.         return false;
  35.     }
  37.     // 从下标 index 开始, 向字符数组左侧寻找下一个有效字符, 其中 # 代表一个退格键, 若不存在有效字符, 则返回 -1
  38.     public int nextIndex(char[] chars, int index) {
  39.         int count = 0;
  40.         while (index >= 0) {
  41.             if (chars[index] == '#') {
  42.                 count++;
  43.             } else {
  44.                 if (count > 0) {
  45.                     count--;
  46.                 } else {
  47.                     break;
  48.                 }
  49.             }
  50.             index--;
  51.         }
  53.         return index;
  54.     }
  55. }
// https://leetcode-cn.com/problems/backspace-string-compare/solution/844zhan-mo-ni-yu-kong-jian-geng-you-de-shuang-zhi-/
class Solution {
    boolean backspaceCompare(String s, String t) {
        int sSkipNum = 0; // 记录 s 的#数量
        int tSkipNum = 0; // 记录 t 的#数量
        int i = s.length() - 1;
        int j = t.length() - 1;

        while (true) {
            while (i >= 0) { // 从后向前，消除 s 的#
                if (s.charAt(i) == '#') sSkipNum++;
                else {
                    if (sSkipNum > 0) sSkipNum--;
                    else break;
                }
                i--;
            }

            while (j >= 0) { // 从后向前，消除T的#
                if (t.charAt(j) == '#') tSkipNum++;
                else {
                    if (tSkipNum > 0) tSkipNum--;
                    else break;
                }
                j--;
            }

            // 后半部分#消除完了，接下来比较S[i] != T[j]
            if (i < 0 || j < 0) break; // s 或者T 遍历到头了
            if (s.charAt(i) != t.charAt(j)) return false;
            i--;j--;
        }

        // 说明S和T同时遍历完毕
        if (i == -1 && j == -1) return true;
        return false;
    }
}

REF

https://leetcode-cn.com/problems/backspace-string-compare
https://leetcode-cn.com/problems/backspace-string-compare/solution/844zhan-mo-ni-yu-kong-jian-geng-you-de-shuang-zhi-/