# 【LeetCode】 844. Backspace String Compare

## Description
> Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.
> Note:
1 <= S.length <= 200
1 <= T.length <= 200
S and T only contain lowercase letters and '#' characters.

> 給兩個字串S和T，回傳他們是否相同。#符號代表一個倒退字元(Backspace鍵)。
> 注意：
> S和T長度都介於1到200
> S和T只會包含小寫字母和'#'符號。

## Example:

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 = "#a#c"
Output: true
Explanation: Both S and T become "c".


Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

## Solution

* 這題如果只是要解題超級簡單，你慢慢硬爆也可以，但是我們要挑戰時間複雜度為`O(N)`和空間複雜度`O(1)`。
* 也就是說，不能有雙重for loop也不能產生額外的陣列去存新的字串來處理。
* 既然不能開額外的字串，那麼我們就要直接對原字串`S`和`T`處理。
* 我建議從尾巴往回看:
* 優點是for的判斷式不會因為erase亂掉，且不用處理多餘的`#`。
* 缺點是要另外記錄現在有多少`#`還沒使用，以免在連續的`#`發生錯誤。

### Code

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int count = 0;
        for(int i = S.size() - 1; i >= 0; i--)
            if(S[i] == '#')
            {
                S.erase(S.begin() + i);
                count++;
            }
            else if(count > 0)
            {
                S.erase(S.begin() + i);
                count--;
            }
        count = 0;
        for(int i = T.size() - 1; i >= 0; i--)
            if(T[i] == '#') 
            {
                T.erase(T.begin() + i);
                count++;
            }
            else if(count > 0)
            {
                T.erase(T.begin() + i);
                count--;
            }
        return S == T;
    }
};

###### tags: `LeetCode` `C++`