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 t combined,

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

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏