Backspace String Compare Leetcode

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)