這題 844. Backspace String Compare 我們需要比較兩個包含 backspace （#）的字串，判斷它們是否相等。

題目：
給定兩個字串 s 和 t，其中 # 表示 backspace 操作，即刪除當前字串最後一個字母。我們要判斷在應用所有 backspace 後，這兩個字串是否相等。

範例：

輸入: s = "ab#c", t = "ad#c"
輸出: true
解釋: s 和 t 都會變成 "ac"

解題思路

backspacing 刪除就表示要紀錄前次的字元，但 backspacing 可能不只一兩個，所以記住所有的歷史，以至於可以回朔操作，

直覺就想到要用 stack 來存放歷史，然後 s 與 t 都有各至的歷史紀錄好像也沒有共用的可能性，

還要考慮到 s 與 t 的長度可能會不一樣長，因次要分開迴圈做

判斷推進 stack 的條件式要寫好，不要把 '#' 給推進 stack 了，注意下列這種組合，

s="y#fo##f"
t="y#f#o##f"

實作：

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        stack<char> sStk;
        stack<char> tStk;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '#') {
                if (!sStk.empty())
                    sStk.pop();
            } else
                sStk.push(s[i]);
        }
        for (int i = 0; i < t.size(); i++) {
            if (t[i] == '#') {
                if (!tStk.empty())
                    tStk.pop();
            } else
                tStk.push(t[i]);
        }
        return sStk == tStk;
    }
};

時間複雜度：O(n)
空間複雜度：O(n)

參考：
#844. Backspace String Compare