Backspace String Compare

Patrick Leaton
Published: April 14, 2021, 3:18 a.m.
Problem Description

Given two strings S and T, return 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 = "#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".

Note:

  • 1 <= S.length <= 200
  • 1 <= 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?

 

The description was taken from https://leetcode.com/problems/backspace-string-compare/.

Problem Solution

#O(M + N) Time, O(1) Space
class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        s_count = t_count = 0
        s_pointer, t_pointer = len(S)-1, len(T)-1
 
        while s_pointer >= 0 or t_pointer >=0:
 
            while s_pointer >=0 and (S[s_pointer] == "#" or s_count > 0):
                if S[s_pointer] == "#":
                    s_count += 1
                else:
                    s_count -=1
                s_pointer -= 1
 
            while t_pointer >=0 and (T[t_pointer] == "#" or t_count > 0):
                if T[t_pointer] == "#":
                    t_count += 1
                else:
                    t_count -=1
                t_pointer -= 1
 
            if S[s_pointer] != T[t_pointer]:
                return False
 
            if (s_pointer>=0) != (t_pointer>=0):
                return False
 
            s_pointer -= 1
            t_pointer -= 1
 
        return True

Problem Explanation

A good approach would be to use a stack that we'd push characters from the input string into and pop the last character off each time we see a pound sign.  That is likely the algorithm that was in mind when this problem was set to easy.

A constant space approach is to use traverse the strings backward using two pointers and a counter to keep track of backspaces.

Let's start by initializing these counters and pointers for each string.

        s_count = t_count = 0
        s_pointer, t_pointer = len(S)-1, len(T)-1

 

We will also create an outer loop that while run while one of the pointers is still in bounds of the string.

        while s_pointer >= 0 or t_pointer >=0:

 

Within the outer loop, we will have two inner loops.  

The outer loop will decrement the pointers once valid characters have been compared.

The inner loops will move the pointers to skip characters that have been backspaced and yield valid characters.

The first inner loop will run while the first string's pointer is still in bounds, and the pointer is at a pound sign or the s_count is greater than zero indicating that we need to skip a character.

            while s_pointer >=0 and (S[s_pointer] == "#" or s_count > 0):

 

If the current pointer is at a pound sign, we will increment the count of pound signs for the first string.

                if S[s_pointer] == "#":
                    s_count += 1

 

Otherwise, we are in this loop because our pound sign count indicates we need to backspace a character, so we will decrement the count.

                else:
                    s_count -=1

 

Once we have handled the counter, we will decrement our pointer to skip this character.

                s_pointer -= 1

 

Basically, the two characters we are not wanting in our final strings for comparison are the characters that we need to backspace, as well as the pound signs themselves.  This is why we require the counter and the check for pound signs to know if we need to skip the current character.

 

We'll do the same thing in the second inner loop, but for the second string.

            while t_pointer >=0 and (T[t_pointer] == "#" or t_count > 0):
                if T[t_pointer] == "#":
                    t_count += 1
                else:
                    t_count -=1
                t_pointer -= 1

 

Once both pointers have been moved to valid characters, we will compare these two characters.

If they are not equal, then we will return false.

            if S[s_pointer] != T[t_pointer]:
                return False

 

If we have a valid pointer that has traversed its entire string while the other valid one hasn't, then we will return false due to a different length of final strings.

            if (s_pointer>=0) != (t_pointer>=0):
                return False

 

Once we have compared the two valid characters, we will decrement both counters to compare the next two characters within the following iteration.

This will continue until we break from the outer loop or return false.

            s_pointer -= 1
            t_pointer -= 1

 

If we have broken from the loop and haven't returned false then both final strings are the same and we can return true.

        return True