# 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: