比较含退格的字符串 图解题解

这道题到底在问什么

输入

s="ab#c", t="ad#c"

输出

true(都变成 "ac")

输入

s="ab##", t="c#d#"

输出

true(都变成空串)

输入

s="a#c", t="b"

输出

false("c" 与 "b")

最优解：一步一步想明白

1. 3记住「从右往左 + skip 计数,找有效字符两两比」。为什么从右往左?因为退格只影响它左边的字符,从右扫才能当场算清谁被删。
2. 4先看 s。指针从最右第 7 位起步,带一个 skip=0。下面一格一格往左走,边走边算哪些字符真正留下来。
3. 5t 也一样,指针落在最右第 7 位、skip=0。两个串各自找「下一个有效字符」,再把这一对拿来比。
4. 6s 的第 7 位是 "e",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。s 当前化简成 "e"。
5. 7t 的第 7 位是 "e",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。t 当前化简成 "e"。
6. 8把这一对有效字符摆出来比:s 是 "e"、t 是 "e"。一样,接着找下一对。
7. 9s 的第 6 位是 "d",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。s 当前化简成 "de"。
8. 10t 的第 6 位是 "d",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。t 当前化简成 "de"。
9. 11把这一对有效字符摆出来比:s 是 "d"、t 是 "d"。一样,接着找下一对。
10. 12s 的第 5 位是退格键 #,欠一次删除,skip 加到 1。# 本身不是字符,继续往左。
11. 13s 的第 4 位是 "c",可前面还欠着退格(skip 从 1 减到 0),所以它被删掉、灰掉跳过。
12. 14s 的第 3 位是退格键 #,欠一次删除,skip 加到 1。# 本身不是字符,继续往左。
13. 15s 的第 2 位是 "b",可前面还欠着退格(skip 从 1 减到 0),所以它被删掉、灰掉跳过。
14. 16s 的第 1 位是 "a",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。s 当前化简成 "ade"。
15. 17t 的第 5 位是退格键 #,欠一次删除,skip 加到 1。# 本身不是字符,继续往左。
16. 18t 的第 4 位是退格键 #,欠一次删除,skip 加到 2。# 本身不是字符,继续往左。
17. 19t 的第 3 位是 "z",可前面还欠着退格(skip 从 2 减到 1),所以它被删掉、灰掉跳过。
18. 20t 的第 2 位是 "b",可前面还欠着退格(skip 从 1 减到 0),所以它被删掉、灰掉跳过。
19. 21t 的第 1 位是 "a",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。t 当前化简成 "ade"。
20. 22把这一对有效字符摆出来比:s 是 "a"、t 是 "a"。一样,接着找下一对。
21. 23s 的第 0 位是 "x",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。s 当前化简成 "xade"。
22. 24t 的第 0 位是 "x",此刻 skip=0、没有欠账,它就是真正留下的有效字符,标绿。t 当前化简成 "xade"。
23. 25把这一对有效字符摆出来比:s 是 "x"、t 是 "x"。一样,接着找下一对。
24. 26两个串从右扫到头,逐对有效字符全都对得上,s 化简成 "xade"、t 化简成 "xade",完全一样,返回 true。全程只用了两个指针和两个 skip 计数,没有另开字符串,空间 O(1)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def next_char(x, i):
            skip = 0
            while i >= 0:
                if x[i] == '#':
                    skip += 1
                elif skip:
                    skip -= 1
                else:
                    return x[i], i - 1
                i -= 1
            return '', -1
        i, j = len(s) - 1, len(t) - 1
        while i >= 0 or j >= 0:
            a, i = next_char(s, i)
            b, j = next_char(t, j)
            if a != b:
                return False
        return True

#include <string>
using namespace std;
class Solution {
public:
    pair<char,int> nextChar(const string& s, int i) {
        int skip = 0;
        while (i >= 0) {
            if (s[i] == '#') skip++;
            else if (skip) skip--;
            else return {s[i], i - 1};
            i--;
        }
        return {'\0', -1};
    }
    bool backspaceCompare(string s, string t) {
        int i = s.size() - 1, j = t.size() - 1;
        while (i >= 0 || j >= 0) {
            auto a = nextChar(s, i);
            auto b = nextChar(t, j);
            if (a.first != b.first) return false;
            i = a.second; j = b.second;
        }
        return true;
    }
};

import java.util.*;
class Solution {
    private int next(String s, int i, char[] out) {
        int skip = 0;
        while (i >= 0) {
            char c = s.charAt(i);
            if (c == '#') skip++;
            else if (skip > 0) skip--;
            else { out[0] = c; return i - 1; }
            i--;
        }
        out[0] = 0;
        return -1;
    }
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;
        char[] a = new char[1], b = new char[1];
        while (i >= 0 || j >= 0) {
            i = next(s, i, a);
            j = next(t, j, b);
            if (a[0] != b[0]) return false;
        }
        return true;
    }
}

复杂度

面试官可能追问