# LC 844. Backspace String Compare

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

###### tags: `leedcode` `easy` `python` `c++` `Stack` `Two Pointer`

Given two strings <code>s</code> and <code>t</code>, return <code>true</code> if they are equal when both are typed into empty text editors. <code>'#'</code> 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:**

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

**Follow up:** Can you solve it in <code>O(n)</code> time and <code>O(1)</code> space?
## Solution 1 - Stack
#### Python

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def check(src):
            stack = []

            for c in src:
                if c == '#':
                    if stack:
                        stack.pop()
                else:
                    stack.append(c)

            return ''.join(stack)

        return check(s) == check(t)

#### C++

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string a;
        for (char& c: s) {
            if (c == '#') {
                if (a.size() > 0) {
                    a.pop_back();
                }
            } else {
                a += c;
            }
        }

        string b;
        for (char& c: t) {
            if (c == '#') {
                if (b.size() > 0) {
                    b.pop_back();
                }
            } else {
                b += c;
            }
        }
        return a == b;
    }
};

## Solution 2 - Two Pointer (Follow up)
#### Python

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        s_idx, t_idx = len(s), len(t)

        while s_idx >= 0 and t_idx >= 0:
            s_back, t_back = 1, 1
            while s_back > 0:
                s_idx -= 1
                if s_idx >= 0 and s[s_idx] == '#':
                    s_back += 1
                else:
                    s_back -= 1

            while t_back > 0:
                t_idx -= 1
                if t_idx >= 0 and t[t_idx] == '#':
                    t_back += 1
                else:
                    t_back -= 1

            if s_idx >= 0 and t_idx >= 0 and s[s_idx] != t[t_idx]:
                return False

        return s_idx < 0 and t_idx < 0

#### C++

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int p1 = s.size() - 1;
        int p2 = t.size() - 1;
        int skip1 = 0;
        int skip2 = 0;

        while (p1 >= 0 || p2 >= 0) {
            while (p1 >= 0) {
                if (s[p1] == '#') {
                    skip1++;
                    p1--;
                } else if (skip1 > 0) {
                    skip1--;
                    p1--;
                } else {
                    break;
                }
            }

            while (p2 >= 0) {
                if (t[p2] == '#') {
                    skip2++;
                    p2--;
                } else if (skip2 > 0) {
                    skip2--;
                    p2--;
                } else {
                    break;
                }
            }

            if (p1 >= 0 && p2 >= 0 && s[p1] != t[p2]) {
                return false;
            }
            if ((p1 >= 0) != (p2 >= 0)) {
                return false;
            }
            p1--;
            p2--;
        }
        return true;
    }
};

>### Complexity
>m = s.length
>n = t.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(m + n) | O(m + n) |
>| Solution 1 | O(m + n) | O(1) |

## Note
x