Given this array:
['abc', 'defg', 'ab', 'jkl', 'ef']
I want to implement an algorithm that removes all strings that are substring of another string in the array.
'ab' is substring of 'abc'
'ef' is substring of 'defg'
The result should be ['abc', 'defg', 'jkl']
.
What I have tried so far is this:
const removeSubstrings = (input: string[]): string[] => {
if (input.length < 2) return input;
const result = [...input];
let i = 0;
while (i < result.length - 1) {
let j = i + 1;
while (j < result.length && j > i) {
if (result[i].includes(result[j])) {
result.splice(j, 1);
} else if (result[j].includes(result[i])) {
result.splice(i, 1);
j--;
} else {
j++;
}
}
if (j > i) {
i++;
}
}
return result;
};
Do you see any other shorter and performant algorithm (maybe using some pre-implemented js methods)?
3
Answers
While not necessarily performant, you can use
Array#some
in the callback ofArray#filter
.To removes all the substrings from an array and only returns the strings that are not substrings of any other string in the input array:
A simple approach to follow:
i
.i
, a new variable booleanisSubstring
is created and initialized to false.j
is used to compare the string at indexi
with every other string in the input array.j
(other than the one at indexi
) includes the string at indexi
, thenisSubstring
is set totrue
and the inner loop is broken usingbreak;
.isSubstring
is stillfalse
, then the string at indexi
is added to the result array using thepush()
method.You could sort the array by length and check if the actual string is not in one of the result set’s strings.