Backspace String Comparisons: Two Ways To Approach a Common Algorithm

Suppose you're given two strings, "ab#c" and "ad#c". The "#" key is a backspace character, which means it deletes the previous character in the string. Return whether or not the two strings are equal. (The Leetcode problem can be found here.)

For this algorithm, there are two common approaches: using and manipulating arrays, and one that involves a two pointer solution. In this post, I'll walk through both approaches.

Using Arrays

The idea behind this approach is to initialize two empty arrays (one for each inputted string). Then, walk through each inputted string, checking each character. If the character is not "#", then add the character to the array. If it is "#", then pop the last element off of the array. Then, join both of the arrays (turning them into strings), and compare if those strings are equal.

First, we'll initialize the arrays, and write out the return statement. I like to include a return statement when I'm beginning to write out a function so that I always have the purpose of the function in mind while I'm working.

function backspaceCompare(S, T) {
  let sArr = [];
  let tArr = [];
  //...
  return sArr === tArr;
}

Now, we'll create two different for loops, one for each inputted string. We're checking these strings separately, and then we will be modifying their corresponding arrays.

function backspaceCompare(S, T) {
  let sArr = [];
  let tArr = [];
  for (let i = 0; i < S.length; i++) {
    //...
  }
  for (let i = 0; i < T.length; i++) {
    //...
  }
  //...
  return sArr === tArr;
}

Inside the first for loop, we will check if the character we're currently on in the string is "#". If it's not, then we will add that character to the string using .push(). If it is, then we will simply pop off the last element from the sArr array. We can do the same in the second loop with the T input and the tArr.

function backspaceCompare(S, T) {
  let sArr = [];
  let tArr = [];
  for (let i = 0; i < S.length; i++) {
    if (S[i] === "#") {
      sArr.pop();
    } else {
      sArr.push(S[i]);
    }
  }
  for (let i = 0; i < T.length; i++) {
    if (T[i] === "#") {
      tArr.pop();
    } else {
      tArr.push(T[i]);
    }
  }
  //...
  return sArr === tArr;
}

Finally, we will turn the arrays into strings by using .join(""). We do this in order to check if they're equal to each other. In JavaScript, [1, 2, 3] === [1, 2, 3] will return false, but 123 === 123 will return true. The reason behind this is that in JS, the === operator checks if the arrays have the same object reference. Every time an object is created, it points to a different spot in memory, so even if its contents are identical, the spot in memory is different.

function backspaceCompare(S, T) {
  let sArr = [];
  let tArr = [];
  for (let i = 0; i < S.length; i++) {
    if (S[i] === "#") {
      sArr.pop();
    } else {
      sArr.push(S[i]);
    }
  }
  for (let i = 0; i < T.length; i++) {
    if (T[i] === "#") {
      tArr.pop();
    } else {
      tArr.push(T[i]);
    }
  }
  sArr = sArr.join("");
  tArr = tArr.join("");
  return sArr === tArr;
}

This array-based approach has O(n) space complexity and O(n) time complexity.

Two Pointers

The two pointers approach involves walking through both inputted strings. If either string's element is a "#", then we will "skip over" the next element in that string once we get to it. If neither string's element is a "#", then we will check if the strings are equal at those points. If they're not equal, then we can return false. If they are equal, we can continue moving down the string, until there are no more characters in either input to check.

This approach took a little longer for me to grasp, so once I go through the code, I'll use and example and walk through each line of code to show how we reach its output.

The Code

First, we'll want to start at the end of both strings, so we should initialize variables at the length of both strings minus 1 (because they start at the 0 index). We also want to initialize skip counts for each inputted string. Skip counts will enable us to keep track of if we've just seen a "#", and if so, to skip over the next element.

function backspaceCompare(S, T) {
  let i = S.length - 1;
  let j = T.length - 1;
  let sSkipCount = 0;
  let tSkipCount = 0;

 //...

Now, we'll want to initiate a while loop. As long as there are elements left in either string to check, we should keep checking them, so we should do a while loop that continues so long as i OR j are greater than or equal to 0. I'll also use this moment to add a return true line at the end, because inside of my while loop, I'll be checking to see if the characters of each string don't equal each other, which means that if they pass all of the checks in the loop, then they must equal each other.

function backspaceCompare(S, T) {
  let i = S.length - 1;
  let j = T.length - 1;
  let sSkipCount = 0;
  let tSkipCount = 0;

  while (i >= 0 || j >= 0) {
    //...
  }
  return true;
}

Now, we can do the first checks inside of the while loop. The first thing we want to check for is if the current element in the first string equals "#". If it does, then we want to add 1 to our skip count (which we'll later use), and also to decrease the pointer by 1 (aka to get closer to the start of the string).

function backspaceCompare(S, T) {
  let i = S.length - 1;
  let j = T.length - 1;
  let sSkipCount = 0;
  let tSkipCount = 0;

  while (i >= 0 || j >= 0) {
    if (S[i] === "#") {
      sSkipCount++;
      i--;
    } //...
  }
  return true;
}

The next check is to see if the skip count for the first string is greater than 0--as in, we just saw a "#", so this element will be deleted. If the skip count for the S checker is greater than 0, and we're not yet finished checking the S string, then we can decrement the skip count, and also decrement i. Decrementing the skip count basically means we're passing over this element, but the next element still should be checked.

function backspaceCompare(S, T) {
  let i = S.length - 1;
  let j = T.length - 1;
  let sSkipCount = 0;
  let tSkipCount = 0;

  while (i >= 0 || j >= 0) {
    if (S[i] === "#") {
      sSkipCount++;
      i--;
    } else if (sSkipCount > 0 && i >= 0) {
      sSkipCount--;
      i--;
    } //...
  }
  return true;
}

Now, the following two checks are essentially the same, but for the T input.

function backspaceCompare(S, T) {
  let i = S.length - 1;
  let j = T.length - 1;
  let sSkipCount = 0;
  let tSkipCount = 0;

  while (i >= 0 || j >= 0) {
    if (S[i] === "#") {
      sSkipCount++;
      i--;
    } else if (sSkipCount > 0 && i >= 0) {
      sSkipCount--;
      i--;
    } else if (T[j] === "#") {
      tSkipCount++;
      j--;
    } else if (tSkipCount > 0 && j >= 0) {
      tSkipCount--;
      j--;
    } //...
  }
  return true;
}

At this point, if the while loop has gone through all of these if and else-if statements, that means there's still elements to check, the current element in both strings is not "#", and there are no elements to skip over. Now, we can check if the strings at both of the counters are equal to each other. If they are not, then we can return false. Otherwise, we can simply decrement both i and j.

function backspaceCompare(S, T) {
  let i = S.length - 1;
  let j = T.length - 1;
  let sSkipCount = 0;
  let tSkipCount = 0;

  while (i >= 0 || j >= 0) {
    if (S[i] === "#") {
      sSkipCount++;
      i--;
    } else if (sSkipCount > 0 && i >= 0) {
      sSkipCount--;
      i--;
    } else if (T[j] === "#") {
      tSkipCount++;
      j--;
    } else if (tSkipCount > 0 && j >= 0) {
      tSkipCount--;
      j--;
    } else if (S[i] !== T[j]) {
      return false;
    } else {
      i--;
      j--;
    }
  }
  return true;
}

An Example

Now that we have the full written out code for this solution (which has O(n) time and O(1) space), it would be helpful to walk through this code using an example.

Let's say S = "ab#c" and T = "ad#c". We start out with i, j, sSkipCount, and tSkipCount.

Since i >= 0 or j >= 0, we'll enter the while loop. None of the if or else if statements are true, so we end up on else { i--; j-- }.

The while loop is still true, so we enter it again. S[i] === "#", so we will increment the skip count, and decrement i.

The while loop is still true. sSkipCount is greater than 0, and i >= 0, so we'll decrement the skip count, and decrement i.

The while loop is still true. T[j] === "#", so we'll increment the skip count, and decrement j.

The while loop is still true. tSkipCount is greater than 0, and j >= 0, so we'll decrement the skip count, and decrement j.

The while loop is still true. None of the if or else if statements apply, so again we end up at else { i--; j-- }.

The while loop is not true, so we do not enter it. Now, we can just return true.

Please let me know in the comments if you have any questions or alternate solutions!