今天我们来看一下这道算法题，非常详细版。对应力扣上844题，链接：
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 只含有小写字母以及字符 ‘#’
本道题我的思路是：（1）使用双指针i，j和计数器skips，skipt进行逆序操作，寻找退格字符‘#’，如果找到了skips+1，当计数大于0时，就意味着前面的数要被删掉。我将进行非常详细的注解，希望大家有所帮助。（2）使用栈来解决，这个不是本章重点，只是另一个较为简单的思路，学有余力的同学可以看看。
一、双指针法（推荐）
1.先定义一个指针i，j为字符串的大小
int i = s.length() - 1;int j = t.length() - 1;
2.定义s，t两个字符串中的计数器skips、skipt
int skips = 0, skipt = 0;//将计数器初始化为0
3.定义大循环 while (i >= 0 || j >= 0)在i>=0或者j>=0时循环一直继续，直到i或者j<0，遍历结束。
4.内层while循环当s字符串存在时，如果找到含退格’#‘字符串，那么s计数器skips++，同时i–指向下一个字符进行判断。如果skips是大于0的数，那么就意味着要删除前面的字符了，删除完指针i前移。如果指向的既不是’#'，skips也不大于0，那么跳出内层循环。
while (i >= 0) {//当i<0不存在if (s[i] == '#') {skips++;//计数器++i--;} else if (skips > 0) {skips--;i--;} else {break;}}
5.对于t字符串也进行与4一样的while循环
while (j >= 0) {if (t[j] == '#') {skipt++;j--;} else if (skipt > 0) {skipt--;j--;} else {break;}}
6.如果i，j同时存在并且>=0,若s字符串对应的值不等于t字符串对应的值，那么返回false
if (i >= 0 && j >= 0) {if (s[i] != t[j]) {return false;}}
7.如果一个字符串存在，一个字符串已经遍历完了，那么字符串长度肯定不一样，返回false`
if (i >= 0 || j >= 0) {return false;}
8.无论比较结果如何，最后都将 i 和 j 减 1，继续下一轮循环，检查下一组可能的有效字符。
i--, j--;如果整个循环都没有返回false，那么两个字符串经过退格处理后是相等的。返回true。
完整代码：
class Solution {
public:bool backspaceCompare(string s, string t) {int i = s.length() - 1;//定义i在s字符串中长度int j = t.length() - 1;int skips = 0, skipt = 0;//定义计数器while (i >= 0 || j >= 0) {//字符串没比较完的条件while (i >= 0) {//当i<0不存在if (s[i] == '#') {skips++;//给计数器+1i--;//指针往前移动一位} else if (skips > 0) {skips--;//如果这个数不是‘#’，计数器--i--;} else {//既不等于#，skip也不大于0，没有要删除的break;}}while (j >= 0) {//同上if (t[j] == '#') {skipt++;j--;} else if (skipt > 0) {skipt--;j--;} else {break;}}if (i >= 0 && j >= 0) {if (s[i] != t[j]) {//如果s字符串和t值不相等return false;//两个字符串不相等}} else {if (i >= 0 || j >= 0) {//如果s指针移动到头了，t还没有return false;//两个字符串不相等}}i--, j--;//无论结果，都--}return true;}
};
二、栈
栈的思想就是把s、t字符串遍历，然后逐个压入栈中，当遇到#时，把刚进去的那个出栈，要记得判断是否空，如果是空访问栈顶元素top一样，运行错误就会报错。然后当s1，s2不为空的时候，定义s3，s4用来把字符串反转一下，字符串将都会逆序排列（栈出来的是后进先出），再把s1，s2给pop掉。最后return s3==s4，如果两个字符串相等的话就返回true。
完整代码如下：
class Solution {
public:bool backspaceCompare(string s, string t) {stack<char> s1, s2; // 定义两个字符串类型的栈for (int i = 0; i < s.size(); i++) {if (s[i] == '#') {//如果s碰到了#if (!s1.empty()) {s1.pop();//s1不为空时，把栈顶删一个}} else {s1.push(s[i]);//当这个数值不等于#时，入栈}}for (int i = 0; i < t.size(); i++) {//将t字符串和s一样的此操作if (t[i] == '#') {if (!s2.empty()) {s2.pop();}}else {s2.push(t[i]);}}string s3, s4;//定义两个字符串，进行反转while (!s1.empty()) {s3 += s1.top();//当s1不为空时，获取s1顶部元素s1.pop();//把原来的s1出栈}while (!s2.empty()) {s4 += s2.top();//同上s2.pop();}return s3 == s4;//如果反转后的两个字符串相等那么返回true}
};
总结：
本道题我使用了两种方法进行解决，双指针的方法重点在于指针的定义点还有计数器的加加减减，栈主要在于它后进先出，入栈出栈帮我们顺利的实现了删除#元素的特点。这几章重点还是尝试把双指针理解一下，不懂的同学可以画画图试着理解一下，希望我的理解对你有所帮助。
