finding substrings within arrays - javascript

Question

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.

what will be the result of this: ['ab','abc','bc','abbc','bb','abb','ac','ababc','abbbc','bbc'] - the desierd logic is not well defined — yossico
– yossico, Commented Nov 23, 2016 at 8:52
['ab','abc','bc','abb','ababc','abbbc','bbc'], as here you wont find any totally different string array elements — Shyam R
– Shyam R, Commented Nov 23, 2016 at 8:54
why not abbc? ab and bc are substrings of abbc right? — Mr.7
– Mr.7, Commented Nov 23, 2016 at 9:26

Rayon · Accepted Answer · 2016-11-23 08:56:03Z

4

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;
  })
}));

edited Nov 23, 2016 at 8:56

answered Nov 23, 2016 at 8:45

Rayon

36.6k5 gold badges54 silver badges78 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Shyam R Over a year ago

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 R Over a year ago

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?

Rayon Over a year ago

@ShyamSundarR — What do you mean by "already computed value" ?

Shyam R Over a year ago

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

Rayon Over a year ago

@ShyamSundarR — But current element could also be super/sub string of previous array elements right ?

Hoang Do · Accepted Answer · 2016-11-23 08:54:16Z

1

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));

answered Nov 23, 2016 at 8:54

Hoang Do

3351 silver badge14 bronze badges

1 Comment

Hoang Do Over a year ago

You can look at the editted answer above xD. Actually it would work the same as my answer

Nina Scholz · Accepted Answer · 2016-11-23 10:21:04Z

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; }

Collectives™ on Stack Overflow

finding substrings within arrays - javascript

3 Answers 3

5 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related