Backspace String Compare

Problem Statement

LeetCode-844: 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.

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Approach

Let’s discuss two approaches to solve this problem.

Using Two Pointers

The problem can be solved using two pointers approach as mentioned below:

1. Iterate over the strings from the end and keep track of the number of backspaces encountered.
2. If we encounter a #, we increment the backspace count.
3. If we encounter a character, we decrement the backspace count.
4. If the backspace count is greater than 0, we skip the character.
5. Finally, we compare the two strings formed by the two pointers.

Using Stack

Another approach to solve this problem is by using a stack as mentioned below:

1. Iterate over the string and push the characters into the stack.
2. If we encounter a #, we pop the top element from the stack.
3. Finally, we compare the two strings formed by the stack.

Implementation

Here is the code implementation for the above approaches. Let’s start with the two pointers approach:

public boolean backspaceCompare(String s, String t) {
    StringBuilder one = new StringBuilder();
    StringBuilder two = new StringBuilder();
    
    int freq = 0;
    int index = s.length()-1;

    while(index >= 0){
        if(s.charAt(index) == '#'){
            freq++;
        }else if (freq > 0){
            freq--;
        }else{
            one.insert(0, s.charAt(index));
        }
        index--;
    }

    index = t.length()-1;
    freq=0;
    
    while(index >= 0){
        if(t.charAt(index) == '#'){
            freq++;
        }else if (freq > 0){
            freq--;
        }else{
            two.insert(0, t.charAt(index));
        }
        index--;
    }

    return one.toString().equals(two.toString());   
}

And here is the code implementation for the stack approach:

public boolean backspaceCompare(String s, String t) {
    Stack<Character> one = new Stack<>();
    Stack<Character> two = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '#' && !one.isEmpty()) {
            one.pop();
        } else if (c != '#') {
            one.push(c);
        }
    }
    for (char c : t.toCharArray()) {
        if (c == '#' && !two.isEmpty()) {
            two.pop();
        } else if (c != '#') {
            two.push(c);
        }
    }
    return one.toString().equals(two.toString());
}

Complexity Analysis

The time and space complexity for both the approaches is identical due to similar operations performed in both the approaches.

Using Two Pointers:

1. Time Complexity: We are iterating over the strings s and t once. Hence, the time complexity is $O(n)$, where $n$ is the combined length of the strings. This can be considered as $O(M+N)$, where $M$ and $N$ are the lengths of individual strings.
2. Space Complexity: We are using two string builders to store the strings formed by the two pointers. Hence, the space complexity is $O(n)$.

Using Stack:

1. Time Complexity: Similar to the two pointer approach, the complexity remains $O(n)$.
2. Space Complexity: Instead os using the StringBuilder instances, we are using stacks in this approach leading to a similar $O(n)$ space complexity.