loading...
Cover image for Backspace String Comparisons: Two Ways To Approach a Common Algorithm

Backspace String Comparisons: Two Ways To Approach a Common Algorithm

alisabaj profile image Alisa Bajramovic Updated on ・7 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

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.

Truth table with i = 3, sSkipCount = 0, j = 3, tSkipCount = 0

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

Truth table with i = 2, sSkipCount = 0, j = 2, sSkipCount = 0

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

Truth table with i = 1, sSkipCount = 1

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

Truth table with i = 0, sSkipCount = 0

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

Truth table with j = 1, tSkipCount = 1

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

Truth table with j = 0, tSkipCount = 0

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

Truth table with i = -1, sSkipCount = 0, j = -1, tSkipCount = 0

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!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide
 

Isn't the point of having 2 pointers is to have them move together?

I think if you rewrite your if / else chain a little bit and break it out into 2 separate if blocks, then you can always decrease i and j together (at least until one of them reaches 0).

 

Really helpful! Thanks Alisa 😊