skip to Main Content

Given this array:

['abc', 'defg', 'ab', 'jkl', 'ef']

I want to implement an algorithm that removes all strings that are substring of another string in the array.

'ab' is substring of 'abc'
'ef' is substring of 'defg'

The result should be ['abc', 'defg', 'jkl'].

What I have tried so far is this:

  const removeSubstrings = (input: string[]): string[] => {
    if (input.length < 2) return input;
    const result = [...input];
    let i = 0;
    while (i < result.length - 1) {
      let j = i + 1;
      while (j < result.length && j > i) {
        if (result[i].includes(result[j])) {
            result.splice(j, 1);
        } else if (result[j].includes(result[i])) {
            result.splice(i, 1);
            j--;
        } else {
          j++;
        }
      }
      if (j > i) {
        i++;
      }
    }
    return result;
  };

Do you see any other shorter and performant algorithm (maybe using some pre-implemented js methods)?

3

Answers


  1. While not necessarily performant, you can use Array#some in the callback of Array#filter.

    function removeSubstrings(strs) {
      return strs.filter((s, i) => !strs.some((s2, j) => i !== j && s2.includes(s)));
    }
    console.log(removeSubstrings(['abc', 'defg', 'ab', 'jkl', 'ef']));
    Login or Signup to reply.
  2. To removes all the substrings from an array and only returns the strings that are not substrings of any other string in the input array:

    A simple approach to follow:

    • Loops through each string in the array using a for loop with a counter variable i.
    • For each string at index i, a new variable boolean isSubstring is created and initialized to false.
    • Do another for loop with a counter variable j is used to compare the string at index i with every other string in the input array.
    • Check if the string at index j (other than the one at index i) includes the string at index i, then isSubstring is set to true and the inner loop is broken using break;.
    • Then check if isSubstring is still false, then the string at index i is added to the result array using the push() method.
    function removeSubstrings(arr) {
      let result = [];
      for (let i = 0; i < arr.length; i++) {
        let isSubstring = false;
        for (let j = 0; j < arr.length; j++) {
          if (i !== j && arr[j].includes(arr[i])) {
            isSubstring = true;
            break;
          }
        }
        if (!isSubstring) {
          result.push(arr[i]);
        }
      }
      return result;
    }
    
    
    const arr = ['abc', 'defg', 'ab', 'jkl', 'ef'];
    const result = removeSubstrings(arr);
    console.log(result); // ['abc', 'defg', 'jkl']
    Login or Signup to reply.
  3. You could sort the array by length and check if the actual string is not in one of the result set’s strings.

    const
        removeSubstrings = array => array
            .sort(({ length: a }, { length: b }) => b - a)
            .reduce((r, s) => {
                if (!r.some(v => v.includes(s))) r.push(s);
                return r;
            }, []),
        data = ['abc', 'defg', 'ab', 'jkl', 'ef'],
        result = removeSubstrings(data);
    
    console.log(result); // ['abc', 'defg', 'jkl']
    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search