Algorithm Challenge: Fuzzy Search

Question

I recently took part in an algorithm challenge to create a Fuzzy search with the following criteria:

Given a set array, create a function that receives one argument and returns a new array containing only the values that start with either:

A) The argument provided
B) The argument provided but with 1 difference (i.e. 1 incorrect letter)

The array was:
fruits = [apple, apricot, banana, pear, mango, cherry, tomato]

so:

• fuzzySearch('ap') = ['apple, apricot']
• fuzzySearch('app') = ['apple', 'apricot']
• fuzzySearch('appl') = ['apple']
• fuzzySearch('pa') = ['banana', 'mango']

This is the solution I came up with:

const fruits = ['apple', 'apricot', 'banana', 'pear', 'mango', 'cherry', 'tomato']

function fuzzySearch(str) {
  return fruits.filter(fruit => 
      {
             let letterCount = 0
    const fruitLetArr = fruit.toLowerCase().split('')
    const strArr = str.toLowerCase().split('')

    for (var i = 0; i < strArr.length; i++) {
     
        console.log(fruitLetArr[i], strArr[i], i, letterCount)
      if (fruitLetArr[i] !== strArr[i]) letterCount++
      if (letterCount === 2) break;
    }
     if (letterCount < 2) return true
      });
   
}

fuzzySearch(str)

Can anyone think of a faster way that doesn't involve iterating over every value before a solution can be found?

Answer 1

Style points

• You can use a spread operator to split a string into an array. Eg [...string] or iterate over the string directly using a for(const char of string) { loop.

• You have some very poor naming

  The name of the searchable array should not be specific to the string it contains as the search is independent what is searched. You are searching string not fruit

Lower Case?

Are you sure that the search need to be case insensitive? That step can add considerable overhead to the code. If you can avoid the need to convert case do so.

Assuming that you do require case insensitive search, then you should convert the search term str to lower case once outside the filter function rather than every time you check a string.

You ask

"Can anyone think of a faster way that doesn't involve iterating over every value before a solution can be found?""

There are two cases where you can return an array without checking any of the items.

1. When the search string is empty or
2. contains only one character.

However you return a new array and as such you should always return a new array, thus in both cases you would still need to iterate each item even if its just to copy it to an array.

The best time complexity possible is \$O(n)\$ where \$n\$ is the number of items in the search array.

Performance

In terms of performance there are several ways to improve the code.

• You need only test if letterCount (which in your code means unmatched count) is equal to 2 after you increment it. In your function you test it each iteration even when you know it has not changed.

• When comparing characters you can use the simpler method stringA.charCodeAt(i) === strB.charCodeAt(i) as it is quicker than stringA[i] === stringB[i]

• Before iterating a string you can check if that string is 2 or more shorter than search string. If it is then you don't need to check each character as you know it does not have the correct number of characters to match the search.

• As you search each item in a callback function (Array.filter). Rather than break out of the loop in this function, just return the false result. This saves the need to add the additional result check when you exit the function.

• Keep references to arrays and objects as close to the current scope as possible.

  Eg you search a global array fruits, rather than use the global reference pass the array reference to the function.

  A local copy can be accessed quicker than a global copy. This can have substantial performance enhancements depending on the depth of the scope tree.

  This is not just because it has a performance gain. It makes the code more maintainable.

Rewrite

Using the points above for performance and cleaned up some of the naming.

It is on average over 5 times quicker than your original (excluding the console logs). At best it is 100 times faster.

_{Note that the position of the ++ matters. if (!++count) (pre-increment) is not the same as if (!count++) (post-increment)}

function fuzzySearch2(str, strings) {
    const len = str.length;
    if (len <= 1) { return [...strings] }
    str = str.toLowerCase();
    return strings.filter(item => {
        var count = -2;
        if (item.length >= len - 1) {
            item = item.toLowerCase();
            let i = len;
            while (i--) {
                if (str.charCodeAt(i) !== item.charCodeAt(i)) {
                    if (!++count) { return false; }
                }
            }
            return true;
        }
        return false;
    });
}