javascript - 什么是搜索一系列食谱并匹配某些配料表上多个单词的有效方法

Question

var mockRecipes = [{
  "name": "PUMPKIN PEANUT BUTTER CHICKEN SOUP",
  "ingredientsByCategory": [{
      "category": "ingredients",
      "ingredients": [
        "1 (15 ounce) can light coconut milk",
        "1 (15 ounce) can pumpkin puree",
        "1 ½ cups low-sodium chicken broth",
        "½ cup natural creamy peanut butter (just peanuts + salt as the ingredients)"
        "1 tablespoon freshly grated ginger",
        "3 cloves garlic, minced",
        "½ teaspoon cayenne (use only ¼ teaspoon if you don’t like things as spicy)",
        "½ teaspoon salt",
        "Freshly ground black pepper",
        "1 ½ pounds boneless skinless chicken breast",
        "1 yellow onion, diced"
      ]
    },
    {
      "category": "for serving",
      "ingredients": [
        "Fresh chopped cilantro",
        "Roasted chopped peanuts",
        "Cooked brown rice"
      ]
    }
  ],
}];

鉴于以上结构，我想要一个搜索输入，以按名称或成分(无论成分列表中的内容)搜索配方。以下搜索应返回此配方，否则不返回；

Input: pum pe but chi -> returns true because it matches the name
Input: pum pe buts chi -> returns false
Input: coco puree butter cilant -> returns true
Input: cilantro beans -> returns false
Input: co be rice cilant roast yellow 1 -> returns true

只是寻找在没有暴力的情况下实现此目标的最佳方法的一般方向。全部在前端

Answer 1

有比强力更好的方法。您应该管理一个数据结构以帮助您完成此任务。请注意，您应该对收据 list 进行预处理，并为此使用一些内存。
就效率而言，我能想到的最好方法是创建一个字符图。迭代成分/名称字符串，并在每次迭代中继续构建图形对象:
对于每个单词w，迭代单词的字符。将w[0]添加到图形对象的根-

if (!graph[w[0]]) graph[w[0]] = {};

继续迭代该单词的字符，并嵌套填充图:

if (!graph[w[0]][w[1]]...[w[w.length-1]]) graph[w[0]][w[1]]...[w[w.length-1]] = {};

对成分中的每个单词都执行相同的操作。请注意，在接下来的迭代中，您可能会与以前的字符冲突，那就完全可以了。就时间复杂度而言，对于 n单词(每个单词都具有 O(1)长度)，构建图表时需要使用 O(n)，并且只要收据不变就可以进行一次构建。
例:
说这是您的收据: 'ingredients': ['pumpkin', 'puree']然后，您的图形将如下所示:

{
  p: {
    u: {
      m: { p: { k: { i: { n: {} } } } },
      r: { e: { e: {} } }
    },
  }
}

在拥有构建此图的初始开销之后，对其进行扫描将非常容易且高效-对于每个输入单词，假设为 pum，逐个遍历图char。如果找不到下一步-不包含这个词。 return (graph.p && graph.p.u && graph.p.u.m)对于 m单词的输入(每个单词的长度为 O(1))，获取 bool(boolean) 值答案将需要 O(m)时间，这是您可以达到的最短时间。
当然，构建图形和以后扫描图形的整个过程都应该是自动化的，并且上面显示的示例不应该手动编写，因为我只是将其用于演示。