2115-从给定原材料中找到所有可以做出的菜

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为
recipes[i] ，如果你有它 所有 的原材料 ingredients[i] ，那么你可以 做出
这道菜。一道菜的原材料可能是 另一道 菜，也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。

同时给你一个字符串数组 supplies ，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。

请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。

注意两道菜在它们的原材料中可能互相包含。

示例 1：

**输入：** recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
**输出：** ["bread"]
**解释：**
我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。

示例 2：

**输入：** recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
**输出：** ["bread","sandwich"]
**解释：**
我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。
我们可以做出 "sandwich" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 。

示例 3：

**输入：** recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
**输出：** ["bread","sandwich","burger"]
**解释：**
我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。
我们可以做出 "sandwich" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 。
我们可以做出 "burger" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 和 "sandwich" 。

示例 4：

**输入：** recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast"]
**输出：** []
**解释：**
我们没法做出任何菜，因为我们只有原材料 "yeast" 。

提示：

  • n == recipes.length == ingredients.length
  • 1 <= n <= 100
  • 1 <= ingredients[i].length, supplies.length <= 100
  • 1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10
  • recipes[i], ingredients[i][j] 和 supplies[k] 只包含小写英文字母。
  • 所有 recipes 和 supplies 中的值互不相同。
  • ingredients[i] 中的字符串互不相同。

方法一：拓扑排序

思路与算法

我们把每一种原材料（菜也算一种原材料）看成图上的一个节点，如果某一道菜需要一种原材料，就添加一条从原材料到菜的有向边。

可以发现，如果图上的一个节点的入度为 0（即不存在以该节点为终点的边），那么该节点对应的原材料是可以直接使用的。特别地，如果该节点对应的原材料是一道菜，那么我们就可以做出这道菜。在这之后，我们将以该节点本身和以该节点为起点的边全部删除，这样就可能会有节点的入度变为 0，我们就可以不断重复这一过程，直到图中不存在节点，或所有剩余节点的入度均不为 0。

上述过程实际上就是使用广度优先搜索进行拓扑排序的过程。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        int n = recipes.size();
        // 图
        unordered_map<string, vector<string>> depend;
        // 入度统计
        unordered_map<string, int> cnt;
        for (int i = 0; i < n; ++i) {
            for (const string& ing: ingredients[i]) {
                depend[ing].push_back(recipes[i]);
            }
            cnt[recipes[i]] = ingredients[i].size();
        }
        
        vector<string> ans;
        queue<string> q;
        // 把初始的原材料放入队列
        for (const string& sup: supplies) {
            q.push(sup);
        }
        // 拓扑排序
        while (!q.empty()) {
            string cur = q.front();
            q.pop();
            if (depend.count(cur)) {
                for (const string& rec: depend[cur]) {
                    --cnt[rec];
                    // 如果入度变为 0，说明可以做出这道菜
                    if (cnt[rec] == 0) {
                        ans.push_back(rec);
                        q.push(rec);
                    }
                }
            }
        }
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        n = len(recipes)
        # 图
        depend = defaultdict(list)
        # 入度统计
        cnt = Counter()
        for i in range(n):
            for ing in ingredients[i]:
                depend[ing].append(recipes[i])
            cnt[recipes[i]] = len(ingredients[i])
        
        ans = list()
        # 把初始的原材料放入队列
        q = deque(supplies)
        
        # 拓扑排序
        while q:
            cur = q.popleft()
            if cur in depend:
                for rec in depend[cur]:
                    cnt[rec] -= 1
                    # 如果入度变为 0，说明可以做出这道菜
                    if cnt[rec] == 0:
                        ans.append(rec)
                        q.append(rec)
        return ans

复杂度分析

  • 时间复杂度：O(dn + m)，其中 m 是数组 supplies 的长度，d 是数组 recipe 中每一个元素（数组）的最大长度，并且我们把所有字符串的长度视为常数。图中会有 n + m 个节点，并且会有不超过 dn 条边，因此建立图以及拓扑排序的时间复杂度为 O(n + m + dn) = O(dn + m)。

  • 空间复杂度：O(dn + m)，即为存储图需要的空间。

 Comments
On this page
2115-从给定原材料中找到所有可以做出的菜