Implement a fuzzy search in JavaScript

Implement a function in JavaScript that performs fuzzy string matching, it accepts an array of strings and a query as input and returns the list of strings that matches.

Example

const strArr = [
  'Doomsayer', 
  'Doomguard', 
  'Doomhamer', 
  'Bane of Doom', 
  'Fearsome Doomguard', 
  'Dr. Boom', 
  'Majordomo', 
  'Shadowbomber', 
  'Shadowform', 
  'Goldshire footman'
];

const query = 'an';

fuzzySearch(strArr, query);

// ["Bane of Doom", "Goldshire footman"]

A string is considered matching if all characters from the search string are found in the string in the same order.

The most complex part of this function is creating the fuzzy search algorithm.

From the problem statement, we understand the that order of characters matters most in the search. Thus we can use the sliding window technique to search in each string.

• Use two variables, one to track the characters of the query and another to track the last searched position in the string.
• Pick the first character from the string, and get its first index in the string from the last searched position, if the character is present, update the last searched position to the current position and keep on check-in further.
• If any of the characters are not present return false, else return true.

const fuzzySearch = function (str, query) {
   // convert the query and str
   // for case-insensitive search
   str = str.toLowerCase();
   query = query.toLowerCase();
  
   // use two variables to track the 
   // current character
   // and last searched position in the string
   let i = 0, lastSearched = -1, current = query[i];
   while (current){ 
      // if the character is not present
      // return false
      if (!~(lastSearched = str.indexOf(current, lastSearched + 1))){
         return false;
      };
     
      current = query[++i];
   };
   
   // if the search completes
   // return true
   return true;
};

Filter all the strings of the array through this function and return the list with the passed ones.

const search = function(arr, query){
  return arr.filter((e) => fuzzySearch(e, query));
};

Test Case

Input:
const arr = [
  'Doomsayer', 
  'Doomguard', 
  'Doomhamer', 
  'Bane of Doom', 
  'Fearsome Doomguard', 
  'Dr. Boom', 
  'Majordomo', 
  'Shadowbomber', 
  'Shadowform', 
  'Goldshire footman'
];

console.log(search(arr, 'sh'));

Output:
["Shadowbomber","Shadowform","Goldshire footman"]