Find All Possible Recipes from Given Supplies — LeetCode 2115 Python Solution

The problem

You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients.

Example

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".

Python solution

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

Pattern: Topological Sort

Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 2115. Find All Possible Recipes from Given Supplies is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.

The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.

Related problems