Finding substrings within arrays

Question

I need to find the substrings within my array. If I have an array: ["abc", "abcd", "abcde", "xyz"], my method should return the array members: abc, abcd, abcde as each is a substring or a superstring of the other, but it should exclude "xyz" as it is not related to other strings in any way.

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

Here my code is of \$O(n^2)\$ complexity, as it's iterating twice over the complete array. Is there any optimal solution?

Answer 1

Interesting question,

• find_substrings should really be findSubstrings
• I dislike arr, and prefer list
• If you sort the array by the length of strings, then you never have to check prior elements
• If you kept a list of matches and non-matches, then you would never have to check matches again
• I found the test case troubling, since you are looking for only 1 set, whereas the code will retrieve any number of sets
• The complexity calculation becomes tricky here, I would think a worst case would be n*n/2, and best case n.

In the end, I came up with something like this:

function findSubstrings(list) {
  var out = [],
    match, rest, i, j;
  //Sort the array by the length of the string
  list.sort((a, b) => a.length - b.length);

  for (i = 0; i < list.length - 1; i++) {
    match = [];
    rest = [];
    for (j = i; j < list.length; j++) {
      if (list[j].indexOf(list[i]) > -1) {
        match.push(list[j]);
      } else {
        rest.push(list[j]);
      }
    }
    //Did we find a set?
    if (match.length > 1) {
      out = out.concat(match);
      list = rest;
      i = 0;
      //Shortcut, should we still bother looking?
      if (rest.length == 0 || rest.length == 1) {
        return out;
      }
    }
  }
  return out;
}
var testCase = ["abc", "abcd", "abcde", "xyz", "tom", "tomd"];
console.log(findSubstrings(testCase));

Answer 2

One quick improvement you can do is to initialize inner for loop variable from
j = i+1 instead of j = 0 and you won't need to check i !== j

for (var j=i+1; j<arr.length; j++)
if (arr[i].indexOf(arr[j]) > -1 || arr[j].indexOf(arr[i]) > -1)