挑戰頁面 - https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3291/
題目原頁面 - https://leetcode.com/problems/backspace-string-compare/

前言

題目有提到可以嘗試看能不能達成時間複雜度 O(N) （其實就是 O(n+m)）和空間複雜度 O(1) ，所以今天的筆記會分成兩個部分記錄。

內容如果有錯誤歡迎指正

直覺第一個想到的解法，新增兩個 stacks 給兩個輸入的字串用
只對原字串動手，不宣告額外的 stacks

1. 直覺第一個想到的解法

資料結構或演算法： Stack

本來想要加上 Two Pointer 但是實質就是各自走訪，加上去感覺有點牽強就沒加了。

概念

核心：看到「會消掉」就可以直接先想到拿 Stack 來用。

圖解的話，以單獨 a#b 為例。為了節省畫面空間這邊把 stack 橫放。

① 從 0 起始，遇到 a, 因為非 # 所以把她 push 到 stack 裡

"a#b"
 *

+-----
| a
+-----

② 前往下個位置，遇到 # ，所以把 top 元素 pop 出來

"a#b"
  *

+-----
| 
+-----

② 前往下個位置，遇到 b ，因為是非 # 所以把她 push 進去

"a#b"
   *

+-----
| b
+-----

③ 指標或稱 index 已經超出範圍，所以轉換 stack 的手續在這邊結束。

步驟

因此，步驟可以歸納為如下

走訪過 S 一次，取得 S 字串的 stack
走訪過 T 一次，取得 T 字串的 stack
比對兩者的 stack 是否相同，並回傳比較結果

Code

根據概念和步驟來把程式碼寫出來，就會如下：

class Solution {
    func backspaceCompare(_ S: String, _ T: String) -> Bool {
        // 步驟 1 - 走訪過 S 一次，取得 S 字串的 stack
        var stackS = [Character]()
        for character in S {
            if character == "#"  {
                if !stackS.isEmpty {
                    stackS.removeLast()
                }
            } else {
                stackS.append(character)
            }
        }

        // 步驟 2 - 走訪過 T 一次，取得 T 字串的 stack
        var stackT = [Character]()
        for character in T {
            if character == "#" {
                if !stackT.isEmpty {
                    stackT.removeLast()
                }
            } else {
                stackT.append(character)
            }
        }

        // 步驟 3 - 比對兩者的 stack 是否相同，並回傳比較結果
        return stackS == stackT
    }
}

複雜度分析

n 為 S 的長度， m 為 T 的長度。

時間複雜度： O(max(m, n))
- 沒有巢狀迴圈，只有進行分別數次走訪，因此取字串長者。
空間複雜度： O(m+n)
- 因為有建立額外兩個 stacks 的關係。

執行結果

Runtime: 8 ms (70.89%)
Memory Usage: 20.9 MB

2. 只對原字串動手

很雞肋的地方就是 Swift 的字串型別無法透過 index 直接取用。這也是 Swift 在處理字串時非常棘手而且無法避免的地方。也導致如果在足夠滿意的執行時間內，空間複雜度還是無法降到 O(1) 。

詳細接著會提到。

概念

先撇掉對 Swift 字串的恩怨情仇，直接針對本質來想吧！

從最直觀的雙 stack 觀察之後，就可以發現可以不需要這樣做。

只要把字串視為一個 stack 即可，操作時，從他的頂端開始操作。接著因為會有連續 # 的情形，所以必須要有個變數來存現在累積幾個 # 。

所以走訪方式的核心概念如下：

Pointer 初始位置為字串最後一個字元的位置。
如果遇到 # 的字元時候，累積計數往上加，並往左邊移動
當遇到非 # 的字元時候，如果累積計數大於 0，意味著需要跳過。因為消耗掉一個 # 所以累積計數減去一，並繼續往左邊移動
如果累計計數是 0 且不是 # 就可以開始跟另外一組比較

這邊先拿一個字串 "a#b" 來解釋就好。

① 第一步驟 count 是 0 ，字元是非 # 可以跟另外一個字串遇到的字元比較。

count: 0
 a#b
   *

② 這邊就把它當成也是 b 於是繼續往左走。這時候遇到 # 於是把 count 加一。

count: 1
 a#b
  *

③ 接著雖然遇到 a 但是原始 count 是 1 ，因此這邊也不比較直接進行到下一個位置

count: 0
 a#b
 *

④ 接著發現他已經超出範圍，在這邊結束走訪和比較。

count: 0
 a#b
*

步驟

把兩個字串都轉換成 Character 陣列

這一部是必要之惡，這一部也是讓空間複雜度變成 O(n+m) 的元兇。
如果設法用字串自己的 subscribe 方式，就是生成頭尾 index、再生成 range 來取得單一字元的話，執行時間會多上六倍左右，因此不是選項。再來是這樣子的寫法也很難理解。

初始化兩個 pointer 為各自的長度 - 1
只要其中一個 pointer 還大於 0 就繼續比較

對 S 執行前大截的步驟，直到找到能夠比較的字元
對 T 執行前大截的步驟，直到找到能夠比較的字元
比較 ①：如果兩個 pointer 都大於 0 ，字元不同的話直接 回傳 false
比較 ②：如果其中一個已經完成全部走訪的話，再比下去也沒有意義所以直接 回傳 false

順利走出走訪和比較的迴圈的話，就可以視為兩個會有同樣結果，所以直接 回傳 true

Code

class Solution {
    func backspaceCompare(_ S: String, _ T: String) -> Bool {

        // 1. 把兩個字串都轉換成 Character 陣列
        var s = Array(S)
        var t = Array(T)

        // 2. 初始化兩個 pointer 為各自的長度 - 1
        var sPointer = S.count - 1
        var tPointer = T.count - 1

        // 初始化 # 個數的計數器
        var sCount = 0
        var tCount = 0

        // 3. 進行走訪和比較
        while sPointer >= 0 || tPointer >= 0 {
            while sPointer >= 0 {
                if s[sPointer] == "#" {
                    sCount += 1
                    sPointer -= 1
                } else if sCount > 0 {
                    sCount -= 1
                    sPointer -= 1
                } else {
                    break
                }
            }

            while tPointer >= 0 {
                if t[tPointer] == "#" {
                    tCount += 1
                    tPointer -= 1
                } else if tCount > 0 {
                    tCount -= 1
                    tPointer -= 1
                } else {
                    break
                }
            }

            // 比較 ①：如果兩個 pointer 都大於 0 ，字元不同的話直接回傳 false
            if sPointer >= 0 && tPointer >= 0 && s[sPointer] != t[tPointer] {
                return false
            }

            // 比較 ②：如果其中一個已經完成全部走訪的話，再比下去也沒有意義所以直接回傳 false
            if (sPointer >= 0) != (tPointer >= 0) {
                return false
            }

            // 前往下個位置
            sPointer -= 1
            tPointer -= 1
        }

        // 4. 順利走出走訪和比較的迴圈的話，就可以視為兩個會有同樣結果，所以可以放心的回傳 true
        return true
    }
}

複雜度分析

n 為 S 的長度， m 為 T 的長度。

時間複雜度: O(m+n)
- 最壞情形就是兩個都左過
空間複雜度: O(m+n)

執行結果

可能是沒有在迴圈中做修改陣列等比較花時間的動作，所以在執行時間上快了很多。

Runtime: 4 ms (94.94%)
Memory Usage: 20.8 MB