JavaScript实现字符串数组模糊搜索

什么是模糊搜索？

模糊搜索是一种技术，它允许你在文本中找到与用户输入接近的结果，即使输入中存在小的错误或字符顺序不完全匹配。这在处理用户可能拼错字或键入字符顺序不一致时特别有用。

实现步骤

接下来，面试官给出了一组字符串数组，要求你在这个数组中实现模糊搜索。你开始思考，决定使用”滑动窗口”技术来解决这个问题。你在面试官的注视下开始编写代码：


const arr = [
    "JavaScript",
    "TypeScript",
    "Python",
    "Java",
    "Ruby on Rails",
    "ReactJS",
    "Angular",
    "Vue.js",
    "Node.js",
    "Django",
    "Spring Boot",
    "Flask",
    "Express.js",
];

面试官点头示意你继续。你明白，要实现这个功能，关键在于编写一个能逐字符检查匹配的函数。于是你写下了如下代码：


const fuzzySearch = (str, query) => {
  str = str.toLowerCase(); // 将字符串转换为小写，确保不区分大小写
  query = query.toLowerCase(); // 同样转换查询字符串
 
  let i = 0, lastSearched = -1, current = query[i];
 
  while (current) {
    // 使用 !~ 来判断当前字符是否在目标字符串中按顺序出现
    if (!~(lastSearched = str.indexOf(current, lastSearched + 1))) {
      return false; // 如果没找到，则返回 false
    }
    current = query[++i]; // 查找下一个字符
  }
  return true; // 如果所有字符都找到，则返回 true
};

什么是滑动窗口？

在编写代码的过程中，你停下来向面试官解释道，滑动窗口是一种常见的算法技巧，特别适用于字符串和数组的处理问题。滑动窗口的核心思想是在数据结构内保持一个“窗口”，逐步滑动窗口的位置进行检查或计算。

在 fuzzySearch 函数中，滑动窗口的概念被用来逐字符地在目标字符串中查找查询字符串中的字符。每次找到一个字符后，搜索的起始位置会向前移动，确保后续字符的匹配不会回到已经匹配过的位置，从而保证字符匹配的顺序性。

代码解释

大小写转换：为了确保搜索时不受大小写影响，你将 str 和 query 都转换为小写。这是为了在比较时忽略大小写的差异。 滑动窗口检查：通过一个循环，你逐个字符检查 query 中的字符是否按顺序出现在 str 中。每次匹配成功后，窗口（即搜索起点）向前滑动，以避免重复匹配之前的字符。 关键操作符 !~：你解释了 !~ 操作符组合的作用。indexOf 返回字符的索引，如果未找到，则返回 -1。~ 操作符将 -1 转为 0，而 ! 操作符将 0 转为 true。这一行代码简洁地判断了字符是否存在于字符串中，并在未找到时直接返回 false。

面试官显然对你的解释感到满意，你继续编写用于过滤整个数组的函数：


const search = function(arr, query) {
  return arr.filter((e) => fuzzySearch(e, query)); // 使用 fuzzySearch 过滤数组
};