LeetCode 题解工作台
从给定原材料中找到所有可以做出的菜
你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] ，如果你有它 所有 的原材料 ingredients[i] ，那么你可以 做出 这道菜。一份食谱也可以是 其它 食谱的原料，也就是说 ingred…
5
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
首先，我们可以将每道菜看成一个节点，每个节点的入度表示其所需的原材料数量。我们可以通过拓扑排序的方式，找到所有可以做出的菜。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
你有 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.length1 <= n <= 1001 <= ingredients[i].length, supplies.length <= 1001 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10recipes[i], ingredients[i][j]和supplies[k]只包含小写英文字母。- 所有
recipes和supplies中的值互不相同。 ingredients[i]中的字符串互不相同。
解题思路
方法一：拓扑排序
首先，我们可以将每道菜看成一个节点，每个节点的入度表示其所需的原材料数量。我们可以通过拓扑排序的方式，找到所有可以做出的菜。
class Solution:
def findAllRecipes(
self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]
) -> List[str]:
g = defaultdict(list)
indeg = defaultdict(int)
for a, b in zip(recipes, ingredients):
for v in b:
g[v].append(a)
indeg[a] += len(b)
q = supplies
ans = []
for i in q:
for j in g[i]:
indeg[j] -= 1
if indeg[j] == 0:
ans.append(j)
q.append(j)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + m + s), where n is the number of recipes, m is the total number of ingredient entries, and s is the number of initial supplies. Space complexity is O(n + m + s) for the hash tables storing recipes, ingredients, and available supplies. |
| 空间 | O(n + m + s) |
面试官常问的追问
外企场景- question_mark
Can you efficiently track which ingredients are available without repeatedly scanning all recipes?
- question_mark
What data structure helps quickly determine if a needed ingredient exists in your current supplies?
- question_mark
How would you handle a recipe that depends on another recipe not yet created?
常见陷阱
外企场景- error
Failing to account for recipes that depend on other recipes as ingredients, causing incorrect availability checks.
- error
Re-scanning all recipes without updating the available ingredients set, leading to unnecessary repeated work.
- error
Not using a hash set for supplies, resulting in O(n*m) lookups instead of O(1) checks per ingredient.
进阶变体
外企场景- arrow_right_alt
Count the number of possible recipes you can make rather than returning the list.
- arrow_right_alt
Given a target recipe, determine the minimal set of supplies needed to create it.
- arrow_right_alt
Handle recipes with circular dependencies and return only recipes that are safe to create.