Leetcode題解 Python：四月挑戰DAY9 Backspace String Compare

給一個字符串，如果遇到「#」，就等於按下Backspace鍵去修改字符串。

如果直接直譯規則書寫，寫起來就是那麼樸實無華且枯燥，這樣也能通過。

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        newS = ""
        for char in S:
            if char == "#":
                if newS: newS = newS[:-1]
            else:
                newS += char
        newT = ""
        for char in T:
            if char == "#":
                if newT:
                    newT = newT[:-1]
            else:
                newT += char    
        return newS == newT

不過呢，題目希望我們能在 O(N)時間 並 O(1)空間 完成。


由於倒退符是往前刪除，因此由後往前對比就可以遇到#字再往前挪動。

指派一個 counter ，遇到 # 就 +1 ，非# 則 -1，使用 while 要跑到 counter 為 0 或是 跑到出界 為止。

這樣就無需使用到 O(N) 空間，用 O(1) 空間。同時也只需要跑一遍 N，花上 O(N) 時間。

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool: 
        # 回車函式
        def getPrev(text, pos):
            backspaceCounter = 1
            while backspaceCounter and pos >= 0:
                pos -= 1                    
                if text[pos] == "#": 
                    backspaceCounter += 1
                else:
                    backspaceCounter -= 1
            if pos >= 0: return pos           
            return -1

        SP, TP = getPrev(S, len(S)), getPrev(T, len(T))

        while SP > -1 and TP > -1:
            if S[SP] != T[TP]: break
            SP, TP = getPrev(S, SP), getPrev(T, TP)

        if TP == -1 and SP == -1: return True
        return False