原题地址（简单）

这题看着是简单难度，可是却把我坑死了。。
开始思路就错了，以为从后向前遍历字符串，来得到删除后的串，结果坑一个接一个。。。。

方法1—模拟

思路

这个题最好的就是这个思路，模拟人类输入字符串的过程，以此构建新的字符串。
然后看一下构建到的两个字符串是否相等。

代码

class Solution {
public:
    string newString(string s) {
        if(s.empty())   return s;
        string res = "";
        for(auto c : s) {
            if(c == '#'){
                if(!res.empty())    res.pop_back();
            }
            else    res += c;
        }
        return res;
    }
    bool backspaceCompare(string S, string T) {
        string newS = "", newT = "";
        newS = newString(S);
        newT = newString(T);
        return newS == newT;
    }
};

时空复杂度

O(N) O(1)

方法2—双指针

思路

这里直接借助了官方的思路。

一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。

具体地，我们定义skip表示当前待删除的字符的数量。每次我们遍历到一个字符：

• 若该字符为退格符，则我们需要多删除一个普通字符，我们让skip 加 1；
• 若该字符为普通字符：
  • 若 skip 为 0，则说明当前字符不需要删去；
  • 若skip 不为 0，则说明当前字符需要删去，我们让 skip 减 1。

这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。

代码

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int len_s = S.size(), len_t = T.size();
        int p = len_s-1, q = len_t-1;
        while(p >= 0 || q >= 0) {
            int skip_s = 0, skip_t = 0;
            while(p >= 0){
                if(S[p] == '#')     skip_s++;
                else if(skip_s)   skip_s--;
                else break;
                p--;
            }
            while(q >= 0){
                if(T[q] == '#')     skip_t++;
                else if(skip_t)   skip_t--;
                else break;
                q--;
            }
            if(p >= 0 && q >= 0 && S[p] == T[q]){
                p--;
                q--;
            }
            else if(p < 0 && q < 0)   return true;
            else return false;
        }
        return true;
    }
};

时空复杂度

同方法1