I need to find the substrings within arrays.
If I have an array: ["abc", "abcd", "abcde", "xyz"]
, the method should return me the array members: "abc", "abcd", "abcde"
as each is a substring or a superstring of the other, but it should exclude "xyz".
What is the best possible method in javascript.
3 Answers
Use Array#filter
var arr = ["abc", "abcd", "abcde", "xyz"];
console.log(arr.filter(function(el) {
return el.indexOf('abc') > -1;
}));
Edit: Use Array#some
if you want to make filter based of some values in the array with respect to current element!
var arr = ["abc", "abcd", "abcde", "xyz"];
console.log(arr.filter(function(el, index) {
return arr.some(function(e, i) {
if (i !== index) {
return e.indexOf(el) > -1 || el.indexOf(e) > -1;
}
return false;
})
}));
-
This is not expected, I need to dynamically compare each element with every other element and see which all are having substrings between each other, the solution you gave finds a pre given text within each array element– Shyam RCommented Nov 23, 2016 at 8:50
-
thanks, this was the one that was expected, but is anyway of using the already computed value for the future checks, by storing them would help in improving the running time?– Shyam RCommented Nov 23, 2016 at 9:02
-
@ShyamSundarR — What do you mean by "already computed value" ?– RayonCommented Nov 23, 2016 at 9:03
-
i mean if i have an array of length 100, I find first few sub/super strings, can I use them further in such a way to reduce all the comparisons dynamically– Shyam RCommented Nov 23, 2016 at 9:09
-
@ShyamSundarR — But current element could also be
super/sub
string of previous array elements right ?– RayonCommented Nov 23, 2016 at 9:15
You can simply use 2 nested loops, but the complexity is O(n^2)
function find_substrings(arr) {
var res = [];
for (var i=0; i<arr.length; i++) {
for (var j=0; j<arr.length; j++) {
if (i !== j && (arr[i].indexOf(arr[j]) > -1 || arr[j].indexOf(arr[i]) > -1)) {
res.push(arr[i]);
break;
}
}
}
return res;
}
var arr = ["abc", "abcd", "abcde", "xyz"];
console.log(find_substrings(arr));
-
You can look at the editted answer above xD. Actually it would work the same as my answer– Hoang DoCommented Nov 23, 2016 at 8:59
You could use some optimized loops with short cut and an object for the items.
var data = ["abc", "abcd", "42", "abcde", "422", "xyz", "q", "1q"],
result = function (array) {
var i, j,
r = {};
for (i = 0; i < array.length - 1; i++) {
if (r[array[i]]) {
continue;
}
for (j = i + 1; j < array.length; j++) {
if (r[array[j]]) {
continue;
}
if (array[i].indexOf(array[j]) !== -1 || array[j].indexOf(array[i]) !== -1) {
r[array[i]] = true;
r[array[j]] = true;
}
}
}
return array.filter(function (a) { return r[a]; });
}(data);
console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }
abbc
?ab
andbc
are substrings ofabbc
right?