Backspace String Compare Leetcode Problem & Solution

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