今天的題目乍看之下也不難,844. Backspace String Compare,第一直覺是可以用 Stack 來寫


給定兩個字串 ST,判斷是否相同,其中#表示退格鍵,所以他的前一個字元當然就被刪掉囉

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

初步想法是當看到#就把前一個 pop 出來,不是就 push 進去,需要注意的是 stack 如果是空的就不能 pop 避免 segment fault,像下面這個 test case 的S有兩次##,其實第二次是沒作用的(沒東西可以刪拉

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

處理完之後就比較一下兩個 Stack 一不一樣,先比長度,再一個一個 pop,如果有不一樣就 False,比到最後就是T

bool backspaceCompare(string S, string T) {
    stack<char> s;
    stack<char> t;
    for(int i=0; i<S.size(); i++) {
        if(S[i] == '#') {
            if(!s.empty())
                s.pop();
        }
        else
            s.push(S[i]);
    }
    
    for(int i=0; i<T.size(); i++) {
        if(T[i] == '#') {
            if(!t.empty())
                t.pop();
        }
        else
            t.push(T[i]);
    }
    
    if(s.size() != t.size())
        return false;
    
    while(!s.empty()){
        if(s.top() != t.top())
            return false;
        s.pop();
        t.pop();
    }
    
    return true;
        
}

這個執行時間是 O(M+N),不過空間也是 O(M+N),題目有提到是否可以用 O(N) 時間&O(1) 空間呢,答案當然是可以的。不過從程式邏輯來說會變得比較複雜,可讀性也不是那麼好懂,除非是真的很需要省時間空間,不然還是建議活用STL就好了。

bool backspaceCompare(string S, string T) {
        int scnt = 0, tcnt = 0;
        int sptr = (int)S.size() - 1;
        int tptr = (int)T.size() - 1;

        while(true){

            while(sptr != -1 && (scnt != 0 || S[sptr] == '#'))
            {
                if(S[sptr] == '#') {
                    scnt++;
                    sptr--;
                } else {
                    if(scnt > 0) {
                        scnt--;
                        sptr--;
                    }
                }
            }

            while(tptr != -1 && (tcnt != 0 || T[tptr] == '#'))
            {
                if(T[tptr] == '#') {
                    tcnt++;
                    tptr--;
                } else {
                    if(tcnt > 0) {
                        tcnt--;
                        tptr--;
                    }
                }
            }

            if(sptr == -1 || tptr == -1){
                if(sptr == -1 && tptr == -1)
                    return true;
                else
                    return false;
            } else {
                if(S[sptr] != T[tptr])
                    return false;
                else {
                    sptr--;
                    tptr--;
                }
            }
        }
        return false;
    }

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料