844. Backspace String Compare

O(n) time O(1) space
从后往前扫，遇到#就处理，直到两个字符串都扫完

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int m = S.length(), n = T.length();
        int i = m - 1, j = n - 1;
        for (; i >= 0 || j >= 0; --i, --j) { // 有可能是["", "ab##"]
            resolve(S, i);
            resolve(T, j);
            if (i < 0 || j < 0 || S[i] != T[j]) break; // 只要有一点不符合要求就break
        }
        return i < 0 && j < 0; // 两个字符串都扫完，说明没有不匹配的字符
    }

    void resolve(const string &s, int &i) {
        for (int cnt = 0; i >= 0; --i) {
            cnt += s[i] == '#' ? 1 : -1; // 类似括号匹配
            if (cnt < 0) return;
        }
    }
};

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int m = S.length(), n = T.length();
        int i = m - 1, j = n - 1;
        for (; i >= 0 || j >= 0; --i, --j) { // 有可能是["", "ab##"]
            resolve(S, i);
            resolve(T, j);
            if (i < 0 || j < 0 || S[i] != T[j]) break; // 只要有一点不符合要求就break
        }
        return i < 0 && j < 0; // 两个字符串都扫完，说明没有不匹配的字符
    }

    void resolve(const string &s, int &i) {
        int cnt = 0;
        while (i >= 0 && s[i] == '#') { // 只要还能继续删就一直处理完
            while (i >= 0 && s[i] == '#') {
                ++cnt;
                --i;
            }
            while (i >= 0 && s[i] != '#' && cnt-- > 0) {
                --i;
            }
        }
    }
};

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        while (!S.empty() || !T.empty()) { // 一定是或不能是与，反例["nzp#o#g", "b#nzp#o#g"]
            resolve(S);
            resolve(T); // resolve完之后要不是空，要不结尾不能是#
            if (S.empty() || T.empty() || S.back() != T.back()) break;
            S.pop_back(); // 因为已经判过空了，所以可以直接pop
            T.pop_back();
        }
        return S.empty() && T.empty();
    }

    void resolve(string &s) {
        int cnt = 0;
        while (!s.empty() && s.back() == '#') { // 一定要处理干净再返回，比如"a#b#" ==> ""而不是"a#"
            while (!s.empty() && s.back() == '#') {
                ++cnt; // 数一下结尾几个#
                s.pop_back();
            }
            while (!s.empty() && s.back() != '#' && cnt > 0) { // 按照#的个数pop结尾字符，直到#个数为0或者字符串为空为止
                s.pop_back();
                --cnt;
            }
        }
    }
};