【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和字符串长度slowIndex。
   int delBackspace(string & s)利用&改变实参s，得到退格处理后的字符串。
   定义两个指针，快指针用来遍历原始字符串，慢指针用来存储处理后的字符串。
   遇到字母，两指针都向前一位，遇到#号，快指针向前一位，需要删除字符，所以慢指针后退一位(注意0位置)。
2. 得到最终字符串后进行比较。
   若最终字符串长度不相等，返回false。
   长度相等则逐一比较。

代码：

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int s_length = delBackspace(s);
        int t_length = delBackspace(t);
        if(s_length != t_length) return false;
        else
        {
            for(int i = 0; i < s_length; i++)
            {
                if(s[i] != t[i]) return false;
            }
        }
        return true;
    }

private:
    // 获取退格处理后的最终字符串长度slowIndex，并且利用&改变实参s，得到退格处理后的字符串
    int delBackspace(string & s)
    {
        // 慢指针代表退格后的字符串长度
        // 快指针遍历字符串
        int slowIndex = 0;
        for(int fastIndex = 0; fastIndex < s.size(); fastIndex++)
        {
            // 遇到字母，两指针都向前一位
            if(s[fastIndex] != '#')
            {
                s[slowIndex++] = s[fastIndex];
            }
            // 遇到#号，快指针向前一位，慢指针后退一位(注意0位置)。
            else
            {
                if(slowIndex > 0)
                {
                    slowIndex--;
                }

            }
        }
        return slowIndex;
    }
};

总结：

时间复杂度：O(A+B+C)，其中 A 和 B 分别为字符串 S 和 T 的长度，C代表处理后的字符串长度。我们需要遍历两字符串和处理后的字符串各一次。
空间复杂度：O(1)。对于每个字符串，我们只需要定义一个指针和长度即可。

1. 首先要获取经过退格字符处理后的最终字符串s和字符串长度slowIndex。
2. 得到最终字符串后进行比较。