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) 的空間。

results matching ""

    No results matching ""