题目描述

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

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

样例

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

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

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

限制

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

算法1

(栈) $O(n + m)$

1. 分别将两个字符串通过栈来确定最终的字符串。
2. 确定字符串过程如下，如果遇到 # 且栈不空时，将一个字符弹栈；如果遇到正常字符，则入栈。
3. 最后比较两个栈是否一致即可。

时间复杂度

• 每个字符串仅遍历一次，故时间复杂度为 $O(n + m)$。

空间复杂度

• 需要额外的栈空间，故空间复杂度为 $O(n + m)$。

C++ 代码

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        stack<int> s1, s2;
        for (char c : s) {
            if (c == '#') {
                if (!s1.empty())
                    s1.pop();
            } else {
                s1.push(c);
            }
        }
        for (char c : t) {
            if (c == '#') {
                if (!s2.empty())
                    s2.pop();
            } else {
                s2.push(c);
            }
        }

        if (s1.size() != s2.size())
           return false;

        while (!s1.empty()) {
            if (s1.top() != s2.top())
                return false;

            s1.pop();
            s2.pop();
        }

        return true;
    }
};

算法2

(倒序扫描) $O(n + m)$

1. 从两个字符串的末尾开始往回扫描，并进行比较。
2. 每一次比较前，需要找到最后一定会出现的字符。找的过程如下，如果当前字符为 #，则退格的次数增加 1；如果遇到其他字符且退格的次数大于 0，则退格的次数减少 1，继续找前一个字符；如果退格的次数为 0，则退出循环，即找到了一定会出现的字符。

时间复杂度

• 每个字符串仅遍历一次，故时间复杂度为 $O(n + m)$。

空间复杂度

• 只需要常数个变量，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int n = s.length(), m = t.length();
        int skipS = 0, skipT = 0;
        int i = n - 1, j = m - 1;

        while (1) {
            while (i >= 0) {
                if (s[i] == '#') {
                    skipS++;
                } else {
                    if (skipS > 0) skipS--;
                    else break;
                }

                i--;
            }

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

                j--;
            }

            if (i < 0 || j < 0)
                break;

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

            i--; j--;
        }

        return i == -1 && j == -1;
    }
};