class Solution {
private:
    int backspace(string &s){
        int i, j;
        for(i=j=0; i<s.length(); ++i){
            if(s[i]=='#'){
                if(j>0) j--;
            }
            else{
                s[j++] = s[i];
            }
        }
        return j;
    }
public:
    bool backspaceCompare(string S, string T) {
        int sLen = backspace(S);
        int tLen = backspace(T);
        if (sLen != tLen) return false;
        for (int i = 0; i < sLen; i++) {
            if (S[i] != T[i]) return false;
        }
        return true;
    }
};