## [844\. Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/)

Given two strings `s` and `t`, return `true` _if they are equal when both are typed into empty text editors_. `'#'` means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

**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".

**Constraints:**

- `1 <= s.length, t.length <= 200`
- `s` and `t` only contain lowercase letters and `'#'` characters.

**Follow up:** Can you solve it in `O(n)` time and `O(1)` space?

- 計數器 for `#` 號，count 多少，就要退幾格
- 遇到 ``#` 號，指針略過繼續走
- 指針從最右到左，其中一個字串沒刪完就繼續刪

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i = s.size() - 1;
        int j = t.size() - 1;

        int s_backspace_count = 0;
        int t_backspace_count = 0;
        
        // 只要其中一個字串沒有掃完，就繼續掃
        while(i >= 0 || j >= 0) {
            while(i >= 0) {
                if(s[i] == '#') {
                    --i;
                    // 要扣掉的數量 + 1
                    ++s_backspace_count;
                } else if(s_backspace_count > 0) {
                    --i;
                    --s_backspace_count;
                } else break;
            }
            while(j >= 0) {
                if(t[j] == '#') {
                    --j;
                    ++t_backspace_count;
                } else if(t_backspace_count > 0) {
                    --j;
                    --t_backspace_count;
                } else break;
            }
            // 如果發現 char 不一樣，直接 return false
            if (i >= 0 && j >= 0 && s[i] != t[j])
                return false;
            
            // 如果都被扣光光了，檢查 i 跟 j 是否相等
            // 這行可以讓程式 early return
            if(i < 0 || j < 0) return i == j;
            --i; --j;
        }
        return i == j;
    }
};

:::success
- 時間複雜度：$O(M + N)$
- 空間複雜度：$O(1)$
:::