Find All Possible Recipes from Given Supplies

LeetCode: https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/

Given recipes and their ingredient lists, and initial supplies, return all recipes you can make. A recipe becomes available when all its ingredients are available.

1from collections import deque
2
3def findAllRecipes(recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
4    graph = {}
5    indeg = {r: 0 for r in recipes}
6    
7    for r, ing in zip(recipes, ingredients):
8        for x in ing:
9            graph.setdefault(x, []).append(r)
10            if x not in indeg:
11                indeg[r] += 1
12    
13    q = deque(supplies)
14    res = []
15    while q:
16        item = q.popleft()
17        for r in graph.get(item, []):
18            indeg[r] -= 1
19            if indeg[r] == 0:
20                res.append(r)
21                q.append(r)
22    return res

Course Schedule II

yeast

flour

meat

recipes=["bread", "sandwich"]

ingredients=Array(2)

supplies=["yeast", "flour", "meat"]

graphEdges=Array(4)

indeg={ bread, sandwich }

queue=["yeast", "flour", "meat"]

res=[]

Step 1 / 6

Step 1:

Build graph ingredient -> recipes and indeg for each recipe.

Focus: select @ [0, 1, 2]