◻️844. Backspace String Compare (easy)

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

---

Solutions

Brute Force

Runtime 4 ms Memory 8.01 MB

```cpp
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int bspace=0;
        string s_dash, t_dash;
        for(int i=s.size()-1; i>=0; --i){
            if(s[i]=='#'){
                ++bspace;
            }
            else if(s[i] != '#' && bspace > 0){
                --bspace;
            }
            else{
                s_dash = s[i] + s_dash;
            }
        }
        bspace=0;
        for(int i=t.size()-1; i>=0; --i){
            if(t[i]=='#'){
                ++bspace;
            }
            else if(t[i] != '#' && bspace > 0){
                --bspace;
            }
            else{
                t_dash = t[i] + t_dash;
            }
        }
        if(s_dash == t_dash) return(true);
        return(false);
    }
};
```

Optimised - 2 Pointer Approach

Runtime 4 ms Memory 7.81 MB

```cpp
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i=s.length()-1, j=t.length()-1;
        int sSkip=0, tSkip=0;
        while(i>=0 || j>=0){
            //s string
            while(i>=0){
                if(s[i]=='#'){
                    sSkip++;
                    i--;
                }
                else if(sSkip>0){
                    sSkip--;
                    i--;
                }
                else break;
            }

            //t string
            while(j>=0){
                if(t[j]=='#'){
                    tSkip++;
                    j--;
                }
                else if(tSkip>0){
                    tSkip--;
                    j--;
                }
                else break;
            }

            if(i>=0 && j>=0 && s[i]!=t[j]) return(false);
            else if((i>=0) != (j>=0)) return(false); // if one string exhaust while other string remain - like: s=bbbextm t=bbb#extm
            --i; --j;
        }
        return(true);
    }
};
```