> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/string/backspace-string-compare.md).

# 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.

```csharp
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`.

```csharp
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)`