LeetCode Solutions Blog

Backspace String Compare

Number: 874

Difficulty: Easy

Paid? No

Problem Description

Given two strings s and t, return true if they are equal when both are typed into empty text editors. The character '#' acts as a backspace which deletes the previous character if it exists. If there is nothing to delete, the backspace does nothing.

Key Insights

'#' represents a backspace operation that deletes the previous character.
A direct simulation using a stack can reconstruct the final string.
A two-pointer approach allows comparison from the end of the strings while skipping backspaced characters.
The two-pointer technique can achieve O(n) time and O(1) space by processing the strings in reverse.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the longer string.
Space Complexity: O(1) using the two-pointer strategy (O(n) if using stacks).

Solution

The solution uses two pointers starting from the end of each string. For each string, maintain a skip counter to account for backspace characters. As you iterate backwards:

If a '#' is encountered, increment the skip counter.
If a normal character is encountered while the skip counter is positive, skip that character by decrementing the counter.
Once a valid character is found, compare the characters from both strings. If all corresponding characters match and both pointers finish processing at the same time, the strings are considered equal.

Code Solutions

# Function to compare two strings with backspace processing
def backspaceCompare(s: str, t: str) -> bool:
    # Pointers for both strings starting at the end
    i, j = len(s) - 1, len(t) - 1
    
    # Process both strings until all characters are compared
    while i >= 0 or j >= 0:
        # Process string s: skip backspaced characters
        skip = 0
        while i >= 0:
            if s[i] == '#':
                skip += 1
                i -= 1
            elif skip > 0:
                skip -= 1
                i -= 1
            else:
                break
        
        # Process string t: skip backspaced characters
        skip = 0
        while j >= 0:
            if t[j] == '#':
                skip += 1
                j -= 1
            elif skip > 0:
                skip -= 1
                j -= 1
            else:
                break
        
        # Compare the current valid characters from s and t
        if i >= 0 and j >= 0:
            if s[i] != t[j]:
                return False
        elif i >= 0 or j >= 0:
            return False
        
        i -= 1
        j -= 1
        
    return True

# Example test cases
print(backspaceCompare("ab#c", "ad#c"))  # Expected output: True
print(backspaceCompare("ab##", "c#d#"))  # Expected output: True
print(backspaceCompare("a#c", "b"))      # Expected output: False