Problem
I wanted to write a function to remove a set of characters from a string in JavaScript.
I came up with this.
How can it be improved in terms of time/space complexity?
function remove(str, chars) {
var set = new Set(chars); // looking up presence of char is O(1)
var arr = [...str]; // operate on an arrray rather than a string to avoid unneccessary string copying
// What follows is O(N) I think...
return arr.reduce((p,c) => {
if(set.has(c)) {
return p;
}
p.push(c);
return p;
}, []).join('');
}
remove('hello world', 'el') === 'ho word';
Solution
- Don’t abuse
reduce
. Reduce should be used when you want to reduce the list. Take using reduce to find the sum of a list:[1, 2, 3].reduce((a, b) => a + b, 0)
. - Use
filter
if you want to filter a list.arr.filter(i => !set.has(i))
. -
You may want to instead use
regex.replace
. However, it’d require checking yourchars
for any regex escape stuff.However if you ignore that, it could be as easy as:
function remove(str, chars) { return str.replace(new RegExp(`[${chars}]`, 'g'), ''); }
Otherwise using the above, for O(n)
time and space complexity, could get you:
function remove(str, chars) {
var set = new Set(chars);
return [...str].filter(i => !set.has(i)).join('');
}