Leetcode 2220 Solution

This article provides solution to leetcode question 2220 (find-all-possible-recipes-from-given-supplies)
Categories:
Tags:
Access this page by simply typing in "lcs 2220" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        supplies = set(supplies)

        recipe_to_ingredients = {}
        for recipe, ingredient_list in zip(recipes, ingredients):
            recipe_to_ingredients[recipe] = ingredient_list

        memo = {}
        def check_elem(elem):
            nonlocal recipe_to_ingredients
            nonlocal supplies

            if elem in memo:
                return memo[elem]

            memo[elem] = False

            valid = True
            if elem in recipe_to_ingredients:
                for child_elem in recipe_to_ingredients[elem]:
                    valid &= check_elem(child_elem)
            else:
                valid = elem in supplies

            memo[elem] = valid
            return valid

        ans = []
        for recipe in recipes:
            if check_elem(recipe):
                ans.append(recipe)
        return ans