Backspace String Compare

Difficulty: Easy | Acceptance: 49.90% | Paid: No Topics: Two Pointers, String, Stack, Simulation

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 editor, the text will continue empty.

• Examples
• Constraints
• Approach 1: Stack Simulation
• Approach 2: Two Pointers

Examples

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.

Approach 1: Stack Simulation

Intuition Simulate the typing process by iterating through each string and using a stack to handle characters and backspaces.

Steps

• Iterate through each character of the string.
• If the character is not ’#’, push it onto the stack.
• If the character is ’#’, pop from the stack if it is not empty.
• After processing both strings, compare the resulting stacks.

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def build(string):
            stack = []
            for char in string:
                if char != '#':
                    stack.append(char)
                elif stack:
                    stack.pop()
            return "".join(stack)
        return build(s) == build(t)

Complexity

• Time: O(N + M), where N and M are the lengths of s and t.
• Space: O(N + M) to store the processed strings.
• Notes: Simple to implement, but uses extra space proportional to the input size.

Approach 2: Two Pointers

Intuition Process the strings from the end to the beginning, skipping characters that are deleted by backspaces, and compare the next valid characters.

Steps

• Initialize two pointers at the end of s and t.
• While pointers are within bounds:
  • Find the next valid character in s by skipping backspaces and the characters they delete.
  • Find the next valid character in t using the same logic.
  • Compare the valid characters. If they differ, return false.
  • If both strings are exhausted, return true.

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i, j = len(s) - 1, len(t) - 1
        while i >= 0 or j >= 0:
            i = self.get_next_valid_index(s, i)
            j = self.get_next_valid_index(t, j)
            if i < 0 and j < 0:
                return True
            if i < 0 or j < 0:
                return False
            if s[i] != t[j]:
                return False
            i -= 1
            j -= 1
        return True

    def get_next_valid_index(self, str, index):
        backspace_count = 0
        while index >= 0:
            if str[index] == '#':
                backspace_count += 1
            elif backspace_count > 0:
                backspace_count -= 1
            else:
                break
            index -= 1
        return index

Complexity

• Time: O(N + M), where N and M are the lengths of s and t.
• Space: O(1), as we only use pointers and counters.
• Notes: Optimal space complexity, though slightly more complex logic than the stack approach.