I got you!

# Problem:

Note that after backspacing an empty text, the text will continue empty.

Example 1:

`Input: s = "ab#c", t = "ad#c"Output: trueExplanation: Both s and t become "ac".`

Example 2:

`Input: s = "ab##", t = "c#d#"Output: trueExplanation: Both s and t become "".`

Example 3:

`Input: s = "a#c", t = "b"Output: falseExplanation: 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)-1s_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 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 —

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

Time Complexity: O(n)

Space Complexity: O(1)

## Pythonic Method —

`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 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 —

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

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

Time Complexity: O(n)

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

# I don’t have friends:

Connect with me on:

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--

## More from Palash Sharma

A student of science | palashsharma891@gmail.com | https://github.com/palashsharma891 | https://www.linkedin.com/in/palashsharma891/