題目 最後的 O(1) space complexity 解答
一開始的思路：用遞增的 index 同時 go through 這兩個字串，按照裡面的 backspace hint build 出兩個新的字串再來看看是否相等
Python 3 solution at first 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 def backspaceCompare (self, s: str, t: str) -> bool: new_t, new_s = '' , '' for i in range(max(len(s), len(t))): try : sc = s[i] except : pass else : if sc == '#' and new_s: new_s = new_s[:len(new_s) - 1 ] elif sc != '#' : new_s += sc try : tc = t[i] except : pass else : if tc == '#' and new_t: new_t = new_t[:len(new_t) - 1 ] elif tc != '#' : new_t += tc return new_t == new_s
缺點：每次遇到 # 就會有個 O(k) 的操作pop() 只有 O(1)，再用 O(m) 的 str.join 合成最終的字串k < n, 1 <= m <= n, n 為字串長度)
Improved Python 3 solution 1 2 3 4 5 6 7 8 9 10 def backspaceCompare (self, s: str, t: str) -> bool: def build (s) : arr = [] for c in s: if c != '#' : arr.append(c) elif arr: arr.pop() return '' .join(arr) return build(s) == build(t)
時間和空間複雜度都是 O(n)
題目的 Follow up: Can you solve it in O(n) time and O(1) space? 思路
不能用額外的 array 來儲存新的字串，那就只能使用 pointer 來 go through 字串，一個個字母依序比較
假如從頭開始 go through 有點困難，因為你不知道當前的字母會不會在之後被刪除，那從後往前可以嗎？
從後往前的話可以。因為只要遇到當前字母之前都沒有 #，該字母就一定會在最終字串裡，而我們一樣可以比較每個字母來判斷兩個字串最終是否相等，當遇到 # 時也可以很容易地跳過
必須要有一個 function for s 和 t，讓我們可以傳入字串和 index，告訴我們：
從那個 index 開始往前的話，下一個合法字母是什麼
下一個 index 從哪邊開始
Final Python 3 solution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 def backspaceCompare (self, s: str, t: str) -> bool: def get_next_char (string: str, index: int) -> tuple: """Helper function to get the next valid character and the next index in the string""" skip = 0 while index >= 0 : if string[index] == '#' : skip += 1 elif skip > 0 : skip -= 1 else : return string[index], index - 1 index -= 1 return None , -1 i = len(s) - 1 j = len(t) - 1 while i >= 0 or j >= 0 : char_s, i = get_next_char(s, i) char_t, j = get_next_char(t, j) if char_s != char_t: return False return True
