一、题目
提示：
1 <= s.length, t.length <= 200
s 和 t 只含有小写字母以及字符 ‘#’
进阶：可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
二、法一：双栈法
如果不考虑用O ( 1 ) O(1)O(1)的空间复杂度，很容易想到这种添加，删除的步骤，可以用到栈的入栈和出栈，所以可以用2个栈模拟2条字符串的退格运算：
class Solution { public: bool backspaceCompare(string s, string t) { stack<char>s1; stack<char>s2; for(int i = 0; i < s.size(); i++){ if(s[i] == '#' && s1.size()!= 0){ s1.pop(); }else if(s[i] != '#'){ s1.push(s[i]); } } for(int i = 0; i < t.size(); i++){ if(t[i] == '#' && s2.size()!= 0){ s2.pop(); }else if(t[i] != '#'){ s2.push(t[i]); } } return s1 == s2; } };
三、法二：双指针法
定义两个双指针，分别指向2个字符串的末尾。
skip表示当前需要待删除的字符个数。
// 挺难的 // 特殊用例 // a a#a 所以要用while (i >= 0 || j >= 0) 要用||，确保碰到满足false的情况，或者双方都遍历完毕 // a ba 返回false的第一种情况，双方skip均为0时进行比较，发现当且仅当一边出界了（可以都出界） // aa aa# 这也是第一种情况 // a b 返回false第二种情况，双方skip均为0时进行比较，发现双方均未出界，但不相等 // 除了上面两种情况，一律返回true // 另一难点，处理#的时候，退出循环的唯一条件就是skip == 0并且不为# class Solution { public: bool backspaceCompare(string S, string T) { int i, j, skipS, skipT; i = S.size() - 1; j = T.size() - 1; skipS = skipT = 0; while (i >= 0 || j >= 0) { while (i >= 0) { if (S[i] == '#') { skipS++; i--; } else if (skipS > 0) { skipS--; i--; } else break; } while (j >= 0) { if (T[j] == '#') { skipT++; j--; } else if (skipT > 0) { skipT--; j--; } else break; } // 此时双方的skip都是0，即应该进行判断（前提是都没出界） if (i >= 0 && j >= 0) { if (S[i] != T[j]) return false; // 返回false的第一个条件 } else { // 至少有一个出界，包含 1. 都出界（不做处理） 2. 当且仅当一个出界（返回false的第二个条件） if (i >= 0 || j >= 0) { // 这行代码表示当且仅当一个出界 return false; } } // 下面这两行容易忘 // 在经历了两轮考察（即判断你是否满足false的条件）之后，如果你满足，就两边各退一步 // 我在官方的基础上加了if语句避免不必要的--操作，虽然不影响最后的答案，但是增强了可读性 // 因为这里的--实质上是针对此时还未出界的指针进行的操作 if (i >= 0) i--; if (j >= 0) j--; } return true; // 执行到这，说明遍历完两边，都没发现满足false的情况，故返回true } };
