Practice/Google/Leetcode 2115. Find All Possible Recipes from Given Supplies

Leetcode 2115. Find All Possible Recipes from Given Supplies

CodingMust

Problem

You are a chef planning which dishes you can prepare based on available ingredients. You have a list of recipes you know how to make, where each recipe requires specific ingredients. Some ingredients might be other recipes you can create, while others must come from your initial supply pantry.

Your task is to determine which recipes can be successfully created given your starting supplies. A recipe can be made if all its required ingredients are either available in your supplies or can themselves be created from other recipes.

Return a list of all recipes that can be created, in any order.

Requirements

1. Each recipe has a corresponding list of ingredients at the same index
2. An ingredient can be either a basic supply item or another recipe name
3. A recipe can only be created if ALL its ingredients are available
4. The output should contain only recipes that can be fully created
5. The order of recipes in the output does not matter

Constraints

• 1 ≤ recipes.length ≤ 100
• 1 ≤ ingredients.length ≤ 100
• recipes.length == ingredients.length
• 1 ≤ supplies.length ≤ 100
• 1 ≤ ingredients[i].length ≤ 10
• All recipe names and supply items are unique strings
• 1 ≤ recipe name length, supply name length ≤ 10
• No recipe will have itself as a direct ingredient

Examples

Example 1:

Input: recipes = ["bread", "sandwich"] ingredients = [["flour", "yeast"], ["bread", "ham"]] supplies = ["flour", "yeast", "ham"] Output: ["bread", "sandwich"] Explanation: We can make bread using flour and yeast from supplies. Then we can make sandwich using the bread we created plus ham from supplies.

Example 2:

Input: recipes = ["soup", "stew", "meal"] ingredients = [["water", "vegetables"], ["meat", "water"], ["soup", "stew", "wine"]] supplies = ["water", "vegetables", "meat"] Output: ["soup", "stew"] Explanation: Both soup and stew can be made from available supplies, but meal cannot be made because wine is not available.

Example 3:

Input: recipes = ["drink_a", "drink_b"] ingredients = [["drink_b", "ice"], ["drink_a", "ice"]] supplies = ["ice"] Output: [] Explanation: drink_a requires drink_b, and drink_b requires drink_a. This circular dependency means neither can be created.