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

🟠   🔖  图 拓扑排序 数组 哈希表 字符串  🔗 力扣 LeetCode

题目

You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes.

You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.

Return a list of all the recipes that you can create. You may return the answer in any order.

Note that two recipes may contain each other in their ingredients.

Example 1:

Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]

Output: ["bread"]

Explanation:

We can create "bread" since we have the ingredients "yeast" and "flour".

Example 2:

Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]

Output: ["bread","sandwich"]

Explanation:

We can create "bread" since we have the ingredients "yeast" and "flour".

We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".

Example 3:

Input: recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]

Output: ["bread","sandwich","burger"]

Explanation:

We can create "bread" since we have the ingredients "yeast" and "flour".

We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".

We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".

Constraints:

• 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], and supplies[k] consist only of lowercase English letters.
• All the values of recipes and supplies combined are unique.
• Each ingredients[i] does not contain any duplicate values.

题目大意

你有 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] 中的字符串互不相同。

解题思路

本题本质上是一个 有向图的可达性问题，其中：

• 节点：所有 recipes 和 supplies。
• 有向边：一个 recipe 指向它的 ingredients。

可以用 DFS + 记忆化搜索 解决：

1. 建图：

   • 维护一个 Set(supplies) 记录当前可用食材。
   • 维护一个 Map(recipeIndex) 记录 recipes 的索引，用于查找 ingredients。

2. DFS 搜索：检查某个食谱是否可制作

   • 终止条件：
     • 若 recipe 直接在 suppliesSet 中，说明已经是可用食材。
     • 若 recipe 不在 recipes 里，说明它无法制作，返回 false。
   • 访问标记：
     • 用 visited 记录当前递归路径，避免循环依赖。
   • 递归检查：
     • 对 recipe 的 ingredients 进行递归 canMake 判断。
   • 记忆化：
     • 若 recipe 可制作，则加入 suppliesSet 以避免重复计算。

3. 遍历所有食谱，调用 canMake 判断哪些可以制作。

复杂度分析

• 时间复杂度：O(n + m)，每个 recipe 和 ingredient 只遍历一次。
• 空间复杂度：O(n + m)，用于 Set 和 Map 存储依赖关系。

代码

/**
 * @param {string[]} recipes
 * @param {string[][]} ingredients
 * @param {string[]} supplies
 * @return {string[]}
 */
var findAllRecipes = function (recipes, ingredients, supplies) {
	const n = recipes.length;
	const suppliesSet = new Set(supplies);
	const recipeIndex = new Map();
	const visited = new Set();
	const result = [];

	// 记录 recipe 的索引
	for (let i = 0; i < n; i++) {
		recipeIndex.set(recipes[i], i);
	}

	// 判断是否能制作某个食谱
	const canMake = (recipe) => {
		if (suppliesSet.has(recipe)) return true; // 已经是原材料
		if (!recipeIndex.has(recipe) || visited.has(recipe)) return false; // 不是食谱 或者 检测过无法制作

		visited.add(recipe); // 标记为正在访问，防止循环依赖
		for (const item of ingredients[recipeIndex.get(recipe)]) {
			if (!canMake(item)) return false;
		}
		visited.delete(recipe); // 解除访问标记

		suppliesSet.add(recipe); // 现在可以制作了，加入 suppliesSet
		result.push(recipe);
		return true;
	};

	// 遍历所有食谱，检查能否制作
	for (const recipe of recipes) {
		canMake(recipe);
	}

	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
210	课程表 II	[✓]	深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
1711	大餐计数		数组 哈希表	🟠	🀄️ 🔗