844. Backspace String Compare
Solution#
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var backspaceCompare = function(s, t) {
let i = s.length - 1;
let j = t.length - 1;
let skipS = 0;
let skipT = 0;
// Loop from back of the strings and count '#'
// so we can skip the correct number of chars
while(i >= 0 || j >= 0) {
while (i >= 0) {
if (s[i] === '#') {
skipS++;
i--;
} else if (skipS > 0) {
skipS--;
i--;
} else {
break
}
}
while (j >= 0) {
if (t[j] === '#') {
skipT++;
j--;
} else if (skipT > 0) {
skipT--;
j--;
} else {
break
}
}
// Chars are different
if (i >= 0 && j >= 0 && s[i] !== t[j]) {
return false;
}
// Compare char with nothing
if ((i >= 0) !== (j >= 0)) {
return false;
}
i--;
j--;
}
return true;
};
Complexity#
- Time Complexity: O(N+M), where N and M are the lengths of
s
and t
.
- Space Complexity: O(1).
All Solutions