Backspace String Compare - Given two strings S and T, return if they are equal

Backspace String Compare - Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character

Given two strings S and T, return 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 = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:

• 1 <= S.length <= 200
• 1 <= T.length <= 200
• S and T only contain lowercase letters and '#' characters.

Follow up:
Can you solve it in O(N) time and O(1) space?

Backspace String Compare Solutions:

Solution 1:

Explanation:

The idea here is that the result is easier to fill than to fill and cut, and since backspace removes previous values, then it's easier for us to turn it all around, in other words, go from the end.

Since there can be several backspaces in a row, we cannot delete previous values, and the best solution would be a counter that will count how many backspaces should be applied to ordinary characters.

To avoid repetition in the code, one function was written that applied the same editing method for both inputs.

/**
 * @param {string} S
 * @param {string} T
 * @return {boolean}
 */
var backspaceCompare = function (S, T) {
  return removeBackspace(S) === removeBackspace(T);
};

const removeBackspace = (array) => {
  let res = [];

  for (let item of array) {
    item === "#" ? res.pop() : res.push(item);
  }

  return res.join("");
};

Solution 2:

Using Javascript ES-6 Syntax

/**
 * @param {string} S
 * @param {string} T
 * @return {boolean}
 */
var backspaceCompare = function (S, T) {
  return removeBackspace(S) === removeBackspace(T);
};

const removeBackspace = (string) =>
  string
    .split("")
    .reduce((result, curr) => {
      curr === "#" ? result.pop() : result.push(curr);
      return result;
    }, [])
    .join("");

Conculsion

Both beats 97.31% run time and 100.00% Memory Usage O(N).

💌 If you’d like to receive more tutorials in your inbox, you can sign up for the newsletter here.