0844-比较含退格的字符串

题目链接

题目描述

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

示例

示例1：

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

提示

• 1 <= S.length <= 200
• 1 <= T.length <= 200

• S 和 T 只含有小写字母以及字符 '#'。

  思路

  思路1：栈模拟

  遍历字符串，从头开始入栈，遇到 # 就弹出一个字符，最后比较得出的两个字符串。

  思路2：双指针

  因为 # 只与其左边的字符有关，所以考虑逆序遍历。维护两个变量 backspaceS 和 backspaceT ，以字符串 s 为例，在遍历过程中：

• 遇到 # 时，backspaceS++；

• 如果遇到字符且 backspaceS 不为0，backspaceS-- ；

• 如果遇到字符且 backspaceS 为0，说明当前字符不会被删除，可以与 字符串 t 比较。

  题解

  思路1：栈模拟

  class Solution {
   private:
    string processString(string s) {
        string ret;
        for (char ch : s) {
            if (ch != '#') {
                ret.push_back(ch);
            } else if (!ret.empty()) {
                ret.pop_back();
            }
        }
        return ret;
    }
   public:
    bool backspaceCompare(string s, string t) {
        return processString(s) == processString(t);
    }
  };

  思路2：双指针

  class Solution {
   public:
    bool backspaceCompare(string s, string t) {
        int i = s.size() - 1;
        int j = t.size() - 1;
        int backspaceS = 0, backspaceT = 0;
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s[i] == '#') {
                    ++backspaceS;
                    --i;
                } else if (backspaceS > 0) {
                    --backspaceS;
                    --i;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (t[j] == '#') {
                    ++backspaceT;
                    --j;
                } else if (backspaceT > 0) {
                    --backspaceT;
                    --j;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {    // 两个字符串都不为空
                if (s[i] != t[j]) {    // 有不相等的元素
                    return false;
                }
            } else {    // 至少有一个不为空
                if (i >= 0 || j >= 0) {    // 只有一个不为空
                    return false;
                }
            }
            --i;
            --j;
        }
        return true;
    }
  };

  复杂度分析

  思路1：栈模拟

• 时间复杂度：

• 空间复杂度：

  思路2：双指针

• 时间复杂度：

• 空间复杂度：