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:
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 soltion can be found?
Here's something that should be slightly more efficient. Also easier to read. In this solution, I am assuming that by "difference" you mean a substitution of a letter for another letter, rather than the addition of another letter.
const fruits = ['apple', 'apricot', 'banana', 'pear', 'mango', 'cherry', 'tomato'];
const fuzzySearch = (str) => {
return fruits.filter((fruit) => {
// If our first case is met, immediately return
if (fruit.startsWith(str)) return true;
// Split the fruit based on the length of input string
const test = fruit.slice(0, str.length).split('');
let diffs = 0;
// Compare + keep track of differences between input + sliced fruit
test.forEach((letter, i) => letter !== str[i] && diffs++);
// If we have more than one difference, it doesn't meet case #2
if (diffs > 1) return false;
return true;
});
};
const testCases = ['ap', 'app', 'appl', 'pan', 'bp'];
for (const testCase of testCases) {
console.log(fuzzySearch(testCase));
}