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\$
4
  • \$\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, 2016 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, 2016 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, 2017 at 3:22
  • \$\begingroup\$ @Thriggle I agree, the requirements are too vague. And a single example is insufficient to clarify the problem statement... \$\endgroup\$ May 24, 2018 at 4:57

2 Answers 2

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\$
2
  • \$\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, 2017 at 23:44
  • \$\begingroup\$ Indeed, you assume probably a sorted array? \$\endgroup\$
    – konijn
    Jun 27, 2017 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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