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)