Backspace String Compare Leetcode

LeetCode Question Link:
https://leetcode.com/problems/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 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".

First Way

const getFormattedString = (input) => {
  const output = [];
  for (let i = 0; i < input.length; i++) {
    if (input[i] === '#') {
      output.pop();
    } else {
      output.push(input[i]);
    }
  }
  return output.join('');
};
const backSpaceCompareFirstWay = (stringOne, stringTwo) => {
  const s = getFormattedString(stringOne);
  const t = getFormattedString(stringTwo);
  if (s === t) {
    return true;
  } else {
    return false;
  }
};

💻 Run Program:

console.log(backSpaceCompareFirstWay('aaa##c', '##ac'));

console.log(backSpaceCompareFirstWay('a###c', 'ac'));

console.log(backSpaceCompareFirstWay('qw#e#e#', '#####q'));

// output
true
false
true

💡 Complexity Major

Time: O(n^2)
Space: O(n)

Second Way

Steps:

• We have used here two-pointer techniques.
• The first pointer p1 is the first string’s last index and p2 is the second string’s last index.
• Use while loop till p1 and p2 is greater than or equal to 0.
• Note: One # means – we have to move back our pointer by 2 indexes.
• If the current char is #, create a variable hashBackCounter with value 2.
• Reduce this variable value by 1 while it becomes 0 and reduce pointer as well.
• In case after reducing pointer by one, next char is also #, then increment hashBackCounter by 2 again.
• Same steps repeat for the second string as well.
• Now at last check chars at same indices and if they are not same, return false else reduce both p1 and p2 by 1.
• The last line returns true.

/**
 *
 * @param {*} s
 * @param {*} t
 * @returns
 */
const backSpaceCompareSecondWay = (s, t) => {
  let p1 = s.length - 1;
  let p2 = t.length - 1;

  while (p1 >= 0 || p2 >= 0) {
    if (s[p1] === '#') {
      let hashBackCounter = 2; // one # means move pointer 2 place back
      while (hashBackCounter > 0) {
        hashBackCounter--;
        p1--;
        if (s[p1] === '#') {
          hashBackCounter += 2;
        }
      }
    }
    if (t[p2] === '#') {
      let hashBackCounter = 2;
      while (hashBackCounter > 0) {
        p2--;
        hashBackCounter--;
        if (t[p2] === '#') {
          hashBackCounter += 2;
        }
      }
    }
    if (s[p1] !== t[p2]) {
      return false;
    } else {
      p1--;
      p2--;
    }
  }
  return true;
};

💡 Complexity Major

Time: O(n)
Space: O(1)

Third way

This program logic is the same as the second way but here we have done code refactoring and move common lines into a separate methods.

const getHashBackPointer = (input, p) => {
  if (input[p] === '#') {
    let hashBackCounter = 2;
    while (hashBackCounter > 0) {
      hashBackCounter--;
      p--;
      if (input[p] === '#') {
        hashBackCounter += 2;
      }
    }
  }
  return p;
};

const backSpaceCompareThirdWay = (s, t) => {
  let p1 = s.length - 1;
  let p2 = t.length - 1;

  while (p1 >= 0 || p2 >= 0) {
    p1 = getHashBackPointer(s, p1);
    p2 = getHashBackPointer(t, p2);
    if (s[p1] !== t[p2]) {
      return false;
    } else {
      p1--;
      p2--;
    }
  }
  return true;
};

💡 Complexity Major

Time: O(n)
Space: O(1)

✔ HashTable Data Structure in JavaScript with Add Delete & Search Algorithms

✔ Trie Data Structure – Insert Search Delete & Print Program with JavaScript

✔ Top JavaScript Commonly asked Algorithms in Interview

✔ JavaScript String Permutation Program with nice explanation

0

0