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.

Solutions

The key idea is to process the strings as if they were being typed into a text editor, where the backspace character removes the previous character.

Approach – Brute Force Technique

This algorithm compares two strings after processing backspaces in them. It uses two stacks to simulate the typing and backspacing process. For each character in the strings, if it's a backspace and the stack is not empty, the top character is removed. If it's not a backspace, the character is added to the stack. After processing both strings, it compares the resulting stacks. If they are equal, it returns true; otherwise, it returns false.

Steps

1. Check for null or empty strings: If either s or t is null or empty, the method returns true. If s is null or empty, it returns false. If t is null or empty, it also returns false.

2. Initialize variables: A character variable backspace is initialized with the value '#'. Two stacks sStack and tStack are created to hold the characters of s and t respectively.

3. Process string s: For each character in s, if the character is a backspace and sStack is not empty, the top character is popped from sStack. If the character is not a backspace, it is pushed onto sStack.

4. Process string t: The same process is repeated for t, but with tStack.

5. Compare stack sizes: If the sizes of sStack and tStack are not equal, the method returns false because the processed strings are of different lengths.

6. Compare stacks: For each item in sStack, the method pops an item from tStack and compares the two. If they are not equal, the method returns false.

7. Return true: If all the above checks pass, the method returns true, indicating that the processed strings s and t are equal.

public class Solution
{
    public bool BackspaceCompare(string s, string t)
    {
        if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t))
        {
            return true;
        }
        if (string.IsNullOrEmpty(s))
        {
            return false;
        }
        if (string.IsNullOrEmpty(t))
        {
            return false;
        }
        char backspace = '#';
        Stack<char> sStack = new();
        Stack<char> tStack = new();

        foreach (var item in s)
        {
            if (item == backspace && sStack.Count > 0)
            {
                sStack.Pop();
            }

            if (item != backspace)
            {
                sStack.Push(item);
            }
        }

        foreach (var item in t)
        {
            if (item == backspace && tStack.Count > 0)
            {
                tStack.Pop();
            }

            if (item != backspace)
            {
                tStack.Push(item);
            }
        }

        if (sStack.Count != tStack.Count)
        {
            return false;
        }

        foreach (var item in sStack)
        {
            var second = tStack.Pop();

            if (item != second)
            {
                return false;
            }
        }

        return true;
    }
  
}

Complexity

• Time complexity: O(S+T)

• Space complexity: O(S+T)

Approach – Two Pointers Technique

Uses two pointers, one for each string, starting from the end and moving backwards. When a pointer encounters a backspace character, it moves back until it finds a non-backspace character. The algorithm then compares these characters. If they're not the same, it returns false. If all compared characters are the same, it returns true.

Steps

1. Initialize two pointers: Start with two pointers, one at the end of each string.

2. Iterate over the strings: Move the pointers backwards through the strings. If a pointer encounters a backspace character, it keeps moving backwards until it finds a non-backspace character. This simulates the effect of the backspace.

3. Compare characters: Once both pointers are pointing to non-backspace characters, compare these characters. If they're not the same, return false.

4. Repeat until pointers meet the start of the strings: Repeat steps 2 and 3 until both pointers have reached the start of their respective strings.

5. Return true: If all compared characters were the same, return true.

public class Solution
{
   public bool BackspaceCompare(string s, string t)
   {
       int i = s.Length - 1, j = t.Length - 1;
       int skipS = 0, skipT = 0;

       while (i >= 0 || j >= 0)
       {
            // While there are characters to compare
           while (i >= 0)
           { // Find position of next possible char in s
               if (s[i] == '#') { skipS++; i--; }
               else if (skipS > 0) { skipS--; i--; }
               else break;
           }
           while (j >= 0)
           { 
               // Find position of next possible char in t
               if (t[j] == '#') { skipT++; j--; }
               else if (skipT > 0) { skipT--; j--; }
               else break;
           }
           // If two actual characters are different
           if (i >= 0 && j >= 0 && s[i] != t[j])
               return false;
           // If expecting to compare char vs nothing
           if ((i >= 0) != (j >= 0))
               return false;
           i--; j--;
       }
       return true;
   }


}

Complexity

• Time complexity: O(S+T)

• Space complexity: O(1)