- 挑戰頁面 - 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