# 【LeetCode】844. Backspace String Compare

## Question link
[Link](https://leetcode.com/problems/backspace-string-compare/description/)

## Intuition
> Given two strings `s` and `t`, return `true` if they are equal when both are typed into empty text editors. `'#'` means a backspace character.
給定兩個字串`s`和`t`，當兩字串都有輸入退格鍵，檢查其是否相等

想像我們正在用鍵盤輸入文字，但在輸入的過程中，你按下了刪除鍵 `#`，這會移除剛剛輸入的最後一個字元。這樣的操作可能會讓我們的輸入內容不斷變化：
* 如果輸入 `abc#d`，它最終會變成 `abd` ，因為 `#` 刪除了`c`。
* 如果輸入 `a#b#`，最後只會留下空字串，因為每個字元都被刪除了。
我們需要模擬這種過程，然後比較兩個字串輸入後的最終結果是否相同。

為了解決這個問題，我們可以用一個技巧來模擬按下刪除鍵的效果：
我們用一個指標`slow` 指向有效字元的位置。每當輸入一個正常字元時，我們把它放到`slow`的位置。
如果遇到刪除鍵 `#`，我們將 `slow` 往回移動，就像把最後輸入的字元「覆蓋掉」。
最終，我們可以得到每個字串處理後的有效部分，再來比較這兩部分是否相等。

## Approach

1. 由於輸入的兩個字串`s`與`t`都需要找到有效字串的部分，因此撰寫一個輔助函數負責找到其有效部分位置，以下是`find_index`實作
* `n` 為字串大小
* `slow` 為輸入字串指向有效字元的部分
* 使用 `fast` 來歷遍整個字串
* 判斷 `fast` 指標是否指向 `#`
* 如果指向 `#` ， `slow` 指標需要模擬被刪除的情況，因次將 `slow` 遞減
* 如果不是就將 `slow` 進行覆蓋成 `fast` 指向的字元並跟更新 `slow`
2. 當找到 `s` 與 `t` 有效部分後便可以逐個位元比較
3. 先判斷有效部分長度是否相同，否則就直接返回 `false`
4. 歷遍整個字串比較是否相同，一遇到不相同就直接反為 `false`
5. 最終返回 `true` ， 表示整個字串都符合

## Complexity
- Time complexity: $O(max(n_1,\ n_2))$
- Space complexity: $O(1)$
## Code

int find_index(char *s)
{
    int n = strlen(s);
    int slow = 0;
    for (int fast = 0; fast < n; fast++) {
        if (s[fast] == '#') { 
            slow = slow == 0 ? 0 : slow - 1;
            continue;
        }
        s[slow++] = s[fast];
    }
    return slow;
};

bool backspaceCompare(char* s, char* t) {
    int s_index = find_index(s);
    int t_index = find_index(t);
    if (s_index != t_index) {
        return false;
    }

    for (int i = 0 ; i < s_index; i++) {
        if (s[i] != t[i]) {
            return false;
        }
    } 
    return true;
};