#844. Backspace String Compare

題目描述

給你兩個字串s和t，如果它們在空白文件編輯器中的顯示的文字是一樣的，回傳true。
#為刪除字元。

如果對一個空白的字串使用刪除，字串還是會維持空白。

限制條件

1. 1 <= s.length, t.length <= 200
2. s和t只會有小寫字元以及#字元。

解題思路

Intuition

這題可以很直覺的判斷出，只要分開處理s和t，先把要進行刪除的字元處理掉，最後再比對兩者是否相等就可以了。

public class Solution { 
	public bool BackspaceCompare(string s, string t) {
        int pos = 0;
        while(s.Length!=pos){
            if(s[pos]=='#'){
                if(pos==0){
                    s=s.Remove(0,1);                    
                }else{
                    s=s.Remove(pos-1,2);                    
                    pos-=1;
                }
                continue;
            }
            pos++;
        }
        pos=0;
        while(t.Length!=pos){
            if(t[pos]=='#'){
                if(pos==0){
                    t=t.Remove(0,1);
                }else{
                    t=t.Remove(pos-1,2);
                    pos-=1;
                }
                continue;
            }
            pos++;
        }        
        return s==t;
    }
}

複雜度分析：

• 時間複雜度：分開處理兩個字串分別要花上s.Length和t.Length的時間，因此時間複雜度為O(m+n)。
• 空間複雜度：C#的String.Remove()會回傳一個新的字串，最糟的情況會使用到s和t最長的那一個字串的空間長度，因此空間複雜度為O(n)。

Follow-up

你可以讓時間複雜度為O(n)以及空間複雜度為O(1)嗎？

Improvement

事實上我們可以由後往前檢查字串，當遇到#的時候，往前減少一格，直到找到下一個可以被比對的字串。

public class Solution { 
	public bool BackspaceCompare(string s, string t) {
        int slen = s.Length-1;
        int tlen = t.Length-1;
        while(slen>=0 || tlen>=0){            
            while(slen>=0 && s[slen]=='#') slen = SkipLetters(s,slen);
            while(tlen>=0 && t[tlen]=='#') tlen = SkipLetters(t,tlen);                              
            if(slen<0 && tlen<0) return true;            
            if((slen<0 && tlen>=0) || (slen>=0 && tlen<0)) return false;
            if(s[slen]!=t[tlen]) return false;            
            slen--;
            tlen--;
        }
        return true;
    }
    public int SkipLetters(string s,int start){
        if(s[start]!='#') return start;
        int count = 1;
        start-=1;        
        while(start>=0 && count!=0){
            if(s[start]=='#') count++;
            else count--;
            start--;
        }
        return start;
    }
}

複雜度分析：

• 時間複雜度：分開處理兩個字串分別要花上s.Length和t.Length的時間，因此時間複雜度為O(m+n)。
• 空間複雜度：沒有任何會增加空間的函式，因此空間複雜度為O(1)。

學習重點

• 字串處裡