844. 比较含退格的字符串 - 力扣（LeetCode）
最终比较的是有效字符串是否相等，所以关键就是如何获取有效字符串。
一开始的思路，类似求字符串的最长子串的思路，利用左右边界的移动，但是写了写觉得不完善，这题是在看栈的时候过来的，所想到了用栈，思路比较明确了：
class Solution { public: stack<int> f(string &s){ stack<int> stk; for(const auto &c : s){ if(c != '#') stk.push(c); else if(!stk.empty()) stk.pop(); } return stk; } bool backspaceCompare(string S, string T) { auto stk1 = f(S); auto stk2 = f(T); if(stk1.size() != stk2.size()) return false; while(!stk1.empty()){ if(stk1.top() != stk2.top()) return false; stk1.pop(); stk2.pop(); } return true; } };不用栈保存有效字符串也是可以的：
class Solution { public: string f(string &s){ string l_tmp; // 用于记录字母个数 int count = 0; for(const auto &c : s){ if(c != '#'){ l_tmp += c; ++count; }else if(count != 0){ l_tmp.erase(l_tmp.end() - 1); --count; } } return l_tmp; } bool backspaceCompare(string S, string T) { return f(S) == f(T); } };不过这个思路时间空间复杂度不难分析均为O(M+N)，M,N为两字符串长度，没法达到进阶要求的空间复杂度O(1)。空间复杂度要为O(1)，必然就不能先保存有效字符串再进行比较了，只能在遍历的时候进行比较，可是仔细一想遍历的时候没法进行比较啊：因为你没法确认当前字符是不是有效的，万一后面有退格符呢？
官方题解思路：
那方法就只有一个了，逆序遍历，可以实现遍历到某字符的时候对其是否有效进行判别，因为逆序的话是可以记录当前字符后面的退格符个数的： （这个代码还是不太好理解的，建议单步走一遍）
class Solution { public: bool backspaceCompare(string S, string T) { // 用于记录退格个数 int s_num = 0, t_num = 0; // 下标或者迭代器逆序遍历，m,n代表下标 int m = S.size() - 1, n = T.size() - 1; while(m >= 0 || n >= 0){ while(m >= 0){ if(S[m] == '#'){ ++s_num; --m; }else if(s_num > 0){ --s_num; --m; }else break; //如果最后一个是字母，就会直接break } while(n >= 0){ if(T[n] == '#'){ ++t_num; --n; }else if(t_num > 0){ --t_num; --n; }else break; //如果最后一个是字母，就会直接break } // 比较“最后”一个字母是否相等 // 注意下标合法性检查 if(m >= 0 && n >= 0 && S[m] != T[n]) return false; if((m >= 0) != (n >= 0)) return false; --m; --n; } return true; } };