5
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ I'm not sure I'm clear on the requirements. Does every element in the returned array need to be a substring or superstring of every other element in the array, or just of at least one other element in the array? \$\endgroup\$ – Thriggle Nov 23 '16 at 16:09
  • 1
    \$\begingroup\$ every element of the array need not to be a substring or superstring of other elements but at lest one element of the array \$\endgroup\$ – Mr.7 Nov 24 '16 at 8:20
  • 2
    \$\begingroup\$ What should be output when array contains more than one related strings e.g. ['abc', 'abcd', 'abcde', 'xyz', 'wxyz', 'vwxyz']? \$\endgroup\$ – Tushar Mar 30 '17 at 3:22
  • \$\begingroup\$ @Thriggle I agree, the requirements are too vague. And a single example is insufficient to clarify the problem statement... \$\endgroup\$ – Igor Soloydenko May 24 '18 at 4:57
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Unfortunately, this change also changes the output of the algorithm. Example: for input ["abc", "ab"] you return ["abc"] while OP returns ["abc", "ab"]. \$\endgroup\$ – le_m Apr 28 '17 at 23:44
  • \$\begingroup\$ Indeed, you assume probably a sorted array? \$\endgroup\$ – konijn Jun 27 '17 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.