# 844. Backspace String Compare — LeetCode(Python)

--

I got you!

# Problem:

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?

# Solution:

## Orthodox Method —

`i, j = len(s)-1, len(t)-1`

s_skip, t_skip = 0, 0

while i >= 0 or j >= 0:

while i >= 0:

if s[i] == '#':

s_skip += 1

i -= 1

elif s_skip > 0:

s_skip -= 1

i -= 1

else:

break

while j >= 0:

if t[j] == '#':

t_skip += 1

j -= 1

elif t_skip > 0:

t_skip -= 1

j -= 1

else:

break

if i >= 0 and j >= 0 and s[i] != t[j]:

return False

if (i >= 0) != (j >= 0):

return False

i -= 1

j -= 1

return True

## Explanation —

We use a two-pointer approach here.

We iterate through the strings while there are characters left in either.

We then, perform basically the same operation on both the strings. We iterate through each string in reverse and get the most recent valid character from the end.

After doing so, both characters from these strings are compared. If they are different, we return *False*, otherwise we carry on for the rest of the strings.

Both *i* and *j *pointers are then decremented.

If the while loop gets terminated, we return *True* because we never came across two different characters at the same time while iterating the two strings.

## Time and Space Complexity —

Since we are checking each character in the string only once, our code runs in linear time. Also, no extra storage was required so, our code uses O(1) extra space.

Thus, if *n* is the length of the two strings ** s** and

**combined,**

*t*Time Complexity: O(n)

Space Complexity: O(1)

## Pythonic Method —

This is basically the same code as above written using Python’s in-built generators.

`def F(S):`

skip = 0

for x in reversed(S):

if x == '#':

skip += 1

elif skip:

skip -= 1

else:

yield x

yield ''

return all(x == y for x, y in zip(F(s), F(t)))

## Explanation —

We use a helper function F() to skip unnecessary symbols.

We run through all characters in both strings and get the most recent valid character. After that we check if both are the same. This check is performed on all valid characters in both strings.

The all() function in Python returns *True* if all items in the iterable are true, and *False* otherwise.

The result of this all() function is returned.

## Time and Space Complexity —

Since we visit all character in both strings only once, our code takes linear time to run.

Also, no extra space is required, we use constant extra space.

Thus, if *n* is the length of the two strings ** s** and

**combined,**

*t*Time Complexity: O(n)

Space Complexity: O(1)