---
tags: data_structure_python
---

# Backspace String Compare <img src="https://img.shields.io/badge/-easy-brightgreen">

Given two strings ```S``` and ```T```, return if they are equal when both are typed into empty text editors. # means a backspace character.

<ins>**Example 1:**</ins>

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

<ins>**Example 2:**</ins>

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

<ins>**Example 3:**</ins>

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

<ins>**Example 4:**</ins>

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

**Note:**

- 1 <= S.length <= 200
- 1 <= 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?

# Solution

### Solution 1: First approach

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        # O(n+m) in time complexity.
        # O(n+m) in space complexity.
        def afterBackspace(word):
            res = ""
            m = len(word)
            
            for i in range(m):
                if word[i] == '#':
                    res = res[:-1]
                else:
                    res = res + word[i]
    
            return res
    
        return afterBackspace(S) == afterBackspace(T)

### Solution 2: Second approach

class Solution(object):
    def backspaceCompare(self, S, T):
        # O(n+m) in time complexity.
        # O(1) in space complexity.
        def F(S):
            skip = 0
            for x in reversed(S):
                if x == '#':
                    skip += 1
                elif skip:
                    skip -= 1
                else:
                    yield x
        
        for x, y in itertools.zip_longest(F(S), F(T)):
            if x != y:
                return False
        return True