# 844. Backspace String Compare

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

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

Approach 1: use a stack to keep the valid characters. O(N) time, O(N) space.

Approach 2: work backwards because we're sure if a char will be deleted from the back. O(N) time, O(1) space.

# Code (Python)

Approach 1:

class Solution:
    def backspaceCompare1(self, S: str, T: str) -> bool:
        # O(N) time, O(N) space
        return self._build(S) == self._build(T)
    
    def _build(self, string):
        stack = []
        for char in string:
            if char == '#':
                if stack:
                    stack.pop()
            else:
                stack.append(char)
        return stack

Approach 2:

    def backspaceCompare(self, S: str, T: str) -> bool:
        # O(N) time, O(1) space
        # idea: work backwards because we're sure if a char will be deleted from the back
        for char_s, char_t in itertools.zip_longest(self._gen_chars(S), self._gen_chars(T)):
            if char_s != char_t:
                return False
        return True
    
    def _gen_chars(self, string):
        i = len(string) - 1
        skips = 0
        while i >= 0:
            if string[i] == '#':
                skips += 1
                i -= 1
                continue
            if skips > 0:
                skips -= 1
            else:
                yield string[i]
            i -= 1

# Code (C++)

Approach 1:

Approach 2: