題目敘述
題目會給定兩個字串s,t，把裡面的井字號#視為鍵盤上的backspace，往前(往左方)吃掉最靠近的字元。
請位最後全部依照規則處理完以後，s,t剩下的字串內容兩者是否相等?例如:
s = "ab#c", t = "ad#c"
說明:
相等，s, t 依照規則操作完，最後都只剩下"ac"。
測試範例
Example 1:
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".
Example 2:
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".
Example 3:
Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".
約束條件
1 <= s.length, t.length <= 200sandtonly contain lowercase letters and'#'characters.
Follow up: Can you solve it in O(n) time and O(1) space?
演算法
基本上這一題和前一個系列題高度相似，換湯不換藥，核心觀念都是在考backspace往前吃字元的操作和對應的stack行為模擬。
從左到右，依序掃描每個字元。
如果遇到普通字元，直接推入stack。
如果遇到井字號#，相當於我們鍵盤上的backspace 往前吃字元的功能，從stack pop出頂端的元素。
最後，留在stack內部的字元，串接在一起轉成字串，字串s, 字串t兩兩比較是否相等就是答案囉!
程式碼
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
stack_s, stack_t = [], []
# --------------------------------------
def final_string( stk, string ):
for char in string:
if char != '#':
# push new character into stack
stk.append( char )
elif stk:
# pop last charachter from stack, as a result of backspace operation
stk.pop()
return ''.join(stk)
# --------------------------------------
return final_string( stack_s, S ) == final_string( stack_t, T )
複雜度分析
時間複雜度: O( m+n )
從頭到尾，每個字元檢查過一遍。
空間複雜度: O( m+n )
需要兩個stack，stack耗用空間最多和輸入字串長度一樣長。
關鍵知識點
在於理解並且活用stack 先進後出FILO的特質，來實作#井字號和普通字元的配對。
記得回去複習 合法括號配對、最長合法括號配對字串長度 、移除星號 這幾題，主要的原理是相通的。
Reference:
[1] Python/JS/Java/C++ O( n ) sol by stack. [w/ Comment] - Backspace String Compare - LeetCode
