---
###### tags: `Leetcode`
---
# Leetcode 844. Backspace String Compare

[link](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?

---

We want to solve it in O(n) time and O(1) space. The first thing that came to my mind was to create a helper function to return the final string after backspacing the characters.

We can create an empty string called 'ans' to store the characters. When we iterate the string, if the current character is equal to '#', then we know we have to push back the character. We can slice the string to omit the last character by using 'ans[:-1]'. Otherwise, we add the character to 'ans'. Finally, we return the result of the comparison.

#### Solution 1

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def type(s):
            ans = ''
            for c in s:
                if c == "#":
                    if len(ans) > 0: ans = ans[:-1]
                else:
                    ans += c

            print(ans)
            return ans

        return type(s) == type(t)
        

O(T): O(n)
O(S): O(1)