844. Backspace String Compare — LeetCode(Python)

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

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store