{x}
blog image

Backspace String Compare

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 Explanation for Backspace String Compare

This problem asks us to compare two strings after applying backspace operations. The optimal approach avoids using extra space (O(1) space complexity) and solves the problem in linear time (O(n) time complexity).

Approach:

The core idea is to use two pointers, one for each string, and iterate backward from the end of each string. We keep track of the number of backspaces encountered for each string. When a non-backspace character is encountered and the backspace count is zero, we compare this character to the corresponding character in the other string. If the characters are different, we return false. Otherwise, we continue iterating backward.

Time Complexity: O(m + n), where m and n are the lengths of strings s and t respectively. We iterate through each string at most once.

Space Complexity: O(1). We use a constant amount of extra space to store the skip counters.

Code Explanation (Python3):

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i, j, skip1, skip2 = len(s) - 1, len(t) - 1, 0, 0  # Initialize pointers and skip counters
 
        while i >= 0 or j >= 0:  # Iterate until both pointers reach the beginning
            while i >= 0: #Handle backspaces in s
                if s[i] == '#':
                    skip1 += 1
                    i -= 1
                elif skip1:
                    skip1 -= 1
                    i -= 1
                else:
                    break
 
            while j >= 0: #Handle backspaces in t
                if t[j] == '#':
                    skip2 += 1
                    j -= 1
                elif skip2:
                    skip2 -= 1
                    j -= 1
                else:
                    break
 
            if i >= 0 and j >= 0:  # Compare characters if both pointers are valid
                if s[i] != t[j]:
                    return False
            elif i >= 0 or j >= 0: #Check if one string still has characters after backspaces
                return False
            i, j = i - 1, j - 1  # Move pointers backward
 
        return True #Strings are equal after backspaces

The code in other languages (Java, C++, Go, TypeScript, Rust) follows the same logic and approach, differing only in syntax and specific language features. The core algorithm remains consistent across all implementations.