算法挑战：模糊搜索

Question

我最近参加了一项算法挑战，使用以下条件创建模糊搜索：

给定一个集合数组，创建一个函数，该函数接收一个参数并返回一个仅包含以以下任一开头的值的新数组：

A）提供的参数 B) 提供了参数，但有 1 个差异（即 1 个不正确的字母）

数组为：fruits = [apple, apricot,banana,pear,mango,cherry,tomato]

所以：

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

这是我想出的解决方案：

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)

有人能想到一种更快的方法，在找到解决方案之前不需要迭代每个值吗？

Answer 1

这是应该稍微更有效率的东西。也更容易阅读。在此解决方案中，我假设“差异”是指用一个字母替换另一个字母，而不是添加另一个字母。

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));
}

轻微更新。实际上没有必要切片水果。我们可以循环输入字符串：

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;

        let diffs = 0;

        // Compare + keep track of differences between input + fruit
        for (let i = 0; i < str.length; i++) {
            if (str[i] === fruit[i]) continue;
            diffs++;
        }

        // If we have more than one difference, it doesn't meet case #2
        return !(diffs > 1);
    });
};

const testCases = ['ap', 'app', 'appl', 'pan', 'bp'];

for (const testCase of testCases) {
    console.log(fuzzySearch(testCase));
}