844.比较含退格的字符串

难度：简单

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

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

示例 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 = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

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

进阶：

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

解题思路

看到退格这个词，我就想到可以用栈来做这个题。

逐字符遍历字符串，如果碰到字符 # 就退栈，碰到小写字母就进栈，同时注意考虑【已经到了栈底，无法继续退栈】的边界情况。

这样当遍历结束的时候，就得到了最终的字符串形态，再直接进行比较即可。

使用栈的代码

java

public boolean backspaceCompare(String s, String t) {
    // 处理两个字符串，考虑退格符的影响
    String processedS = processString(s);
    String processedT = processString(t);
    
    // 比较处理后的字符串是否相等
    return processedS.equals(processedT);
}

// 处理字符串，考虑退格符的影响
private String processString(String str) {
    int pointer = 0;  // 指向结果字符串的下一个字符位置
    char[] result = new char[str.length()]; // 创建字符数组存储最终结果

    for (int i = 0; i < str.length(); i++) {
        char current = str.charAt(i);
        if (current != '#') {
            // 如果当前字符不是退格符，就将其添加到结果中
            result[pointer] = current;
            pointer++;
        } else if (pointer > 0) {
            // 如果是退格符，并且之前有字符，则退格（减少指针）
            pointer--;
        }
    }
    
    // 返回最终结果字符串
    return new String(result, 0, pointer);
}

时间复杂度：O(n+m)，其中 n 和 m 分别为字符串 S 和 T 的长度。我们需要遍历两字符串各一次。

空间复杂度：O(n)，其中 n 是两个输入字符串中较长那个的长度。

上述代码并没有直接使用栈数据结构，而是使用了一个字符数组 result 和一个额外的指针 pointer 来模拟栈的行为，从而有效地处理字符串中的退格符。这种方法的优点是简单且不需要额外的栈数据结构，但它只适用于模拟简单的入栈/出栈操作。

但单纯用栈，空间复杂度不满足题目中 O(1) 的要求，所以在上述算法的基础上，考虑使用双指针来减少空间依赖。

更优思路

一个字符串中某位置的字符是否会被删除，只取决于该字符后面的退格符，而与该字符前面的退格符无关。

由于一个 # 号只会消除其左边的一个字符，对右边的字符无影响，所以当我们选择 从后往前 遍历 s、t 字符串时，就可以立即确定当前字符是否会被删掉。

详细思路：

设定两个指针 sPointer、tPointer 分别为字符串 s、t 中最后一个字符的索引
两个指针都是从后往前遍历字符串，同时设置变量 sSkips 和 tSkips 作为退格计数器，用来记录当前遇到的有效 # 的数量，也就是 当前待删除的字符的数量
使用一个外层的 while 循环，条件是 sPointer 或 tPointer 中至少有一个大于等于0，意味着至少有一个字符串还没有遍历完全。
- 循环内部，我们对字符串 s、t 各使用一个 while 循环来找到当前字符串中下一个有效字符的位置（在从后往前的情况下），即不会由退格符 '#' 删除的字符。
  - 若碰到 # ，则增加退格计数器（sSkips 或 tSkips），并向左移动指针（减少 sPointer 或 tPointer）
  - 若碰到小写字母且退格计数器大于 0，意味着当前字符需要被删除了，则减少退格计数器的值，并向左移动指针
  - 若碰到小写字母且退格计数器等于 0，意味着此时指针指向的正是下一个有效字符，此时退出当前循环，可以开始比较字符了。
- 若两个指针都大于或等于 0，则比较两个字符串在这些位置上的字符。
  - 若字符不相同，则说明字符串已经不相等，返回 false。
  - 若字符相同，则将 sPointer 和 tPointer 向左移动一位（减1），继续外层循环，寻找下一个有效字符。
- 若只有一个指针小于 0，说明一个字符串的有效字符已经遍历完了，而另一个字符串还存在有效字符，则说明字符串已经不相等，返回 false。
如果所有有效字符都相等，且两个字符串同时遍历完毕，则说明字符串相等，返回 true。

更优代码

java

public boolean backspaceCompare(String s, String t) {
    int sPointer = s.length() - 1, tPointer = t.length() - 1;
    int sSkips = 0, tSkips = 0;

    while (sPointer >= 0 || tPointer >= 0) {
        // 找到下一个有效字符的位置或字符串开始位置
        while (sPointer >= 0) {
            if (s.charAt(sPointer) == '#') {
                sSkips++;
                sPointer--;
            } else if (sSkips > 0) {
                sSkips--;
                sPointer--;
            } else {
                break;
            }
        }

        while (tPointer >= 0) {
            if (t.charAt(tPointer) == '#') {
                tSkips++;
                tPointer--;
            } else if (tSkips > 0) {
                tSkips--;
                tPointer--;
            } else {
                break;
            }
        }

        // 比较两个字符串的当前字符
        if (sPointer >= 0 && tPointer >= 0 && s.charAt(sPointer) != t.charAt(tPointer)) {
            return false;
        } else if ((sPointer >= 0) != (tPointer >= 0)) {// 一个字符串的有效字符已经遍历完了，而另一个字符串还存在有效字符
            return false;
        }

        sPointer--;
        tPointer--;
    }

    return true;
}

时间复杂度：O(n+m)，其中 n 和 m 分别为字符串 s 和 t 的长度。我们需要遍历两个字符串各一次。

空间复杂度：O(1)。

总结

逆向遍历字符串的想法不容易想到，而且其边界条件也更加复杂，在对空间复杂度没有需求的时候，第一种做法是更容易想到的。

844.比较含退格的字符串 ​

解题思路 ​

使用栈的代码 ​

更优思路 ​

更优代码 ​

总结 ​

844.比较含退格的字符串

解题思路

使用栈的代码

更优思路

更优代码

总结