# 844 - Backspace String Compare

解法一 - Two Pointer

一開始會想要用兩個 pointer 指向 S 跟 T 的第一個 character，如果兩者指向的 char 相同，那就同時往後：如果指向的 char 不同，那就要往後找 backspace，直到可以確定兩者指的是同一 char。只是這樣做的邏輯會很難寫，因為不知道要往後幾個才夠，例如：

S = "xyyy###z" T = "xz"

如果 S 那邊的 pointer 得走很久才能跟 T 繼續比較，就不是 O(N) 時間複雜度的演算法了。

下一個想法就是，如果兩邊的 pointer 從最後往前走呢？那只要兩邊都已經把當前的 backspace 處理完，卻有：

1. 兩邊的 char 不相同

2. 一邊已經走到底，另一邊還沒走到底

這兩種情況，那就可以知道 S != T。把以上的想法實作出來，就像下面這樣：

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int indexS=S.length()-1, indexT=T.length()-1;

        while(indexS >= 0 || indexT >= 0) {
            int idxS = findValidIndex(S, indexS);
            int idxT = findValidIndex(T, indexT);

            if(idxS < 0 && idxT < 0)
                return true;
            else if(idxS < 0 || idxT < 0)
                return false;
            else if(S[idxS] != T[idxT])
                return false;

            indexS = idxS-1;
            indexT = idxT-1;
        }

        return true;
    }

private:
    int findValidIndex(string str, int index) {
        if(str[index] != '#')
            return index;
        else {
            int bscount = 0;

            while(index >= 0 && str[index] == '#') {
                bscount++;
                index--;
            }

            return index-bscount;
        }
    }
};

不過這個實作方法有一個問題，就是 findValidIndex 的地方不對，我的 findValidIndex 只會處理當前有遇到的 backspace，所以會掛在下面這個 case：

在處理 "a##c" 時，我遇到 c 前面的 #，就會直接回傳 idxS == -2；但遇到 "#a#c" 中 c 前面的 # 時，會回傳的 idxT == 0，所以就會以為 S != T。所以必須改寫 findValidIndex，一次就把所有 backspace 處理掉。

修改後的程式碼如下：

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int indexS=S.length()-1, indexT=T.length()-1;

        while(indexS >= 0 || indexT >= 0) {
            int idxS = findValidIndex(S, indexS);
            int idxT = findValidIndex(T, indexT);

            if(idxS < 0 && idxT < 0)
                return true;
            else if(idxS < 0 || idxT < 0)
                return false;
            else if(S[idxS] != T[idxT])
                return false;

            indexS = idxS-1;
            indexT = idxT-1;
        }

        return true;
    }

private:
    int findValidIndex(string str, int index) {
        int bscount = 0;
        while(index >= 0) {
            if(str[index] == '#') {
                bscount++;
                index--;
            }
            else if(bscount > 0) { // index point to non-bs char, but already have bs 
                bscount--;
                index--;
            }
            else if(bscount == 0){ // index point to non-bs character
                break;
            }
        }

        return index;
    }
};

這個解法比起把兩個 string 的結果都產生出來，可以省下 O(N) 的空間。