844. Backspace String Compare

題目網址：https://leetcode.cn/problems/backspace-string-compare/

題意：給兩個 string s, t, 其中的 # 代表 退格(backspace)字元, 求兩字串是否相等。

Solution：

想法：利用 two pointers, 其中 slowindex 負責 in-place 記錄新的 string, 而 fastindex 負責遍歷整個 string

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        return build(s) == build(t);
    }

private:
    string build(string s){
        int slowindex = 0;
        for (int fastindex = 0; fastindex < s.size(); ++fastindex) {
            if (s[fastindex] == '#') {
                slowindex = max(0, --slowindex);
            } else {
                s[slowindex++] = s[fastindex];
            }
        }
        return s.substr(0, slowindex);
    }
};

• time：$O(m + n)$ ➔ 遍歷 s 和 t, m 為 s 之長度, n 為 t 之長度
• space：$O(1)$ ➔ 只需常數空間