Show problems as
Classic problem #2115MediumArrayHash TableStringGraph TheoryTopological SortDirected Acyclic Graph

Find All Possible Recipes from Given Supplies

Real-world version: Fabrication Cards in a Model Workshop
Tracked in this browser only
Read Find All Possible Recipes from Given Supplies on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A model workshop owns a drawer of components and a book of fabrication cards.

Card i makes the part named builds[i], and running it consumes one of every component named in needs[i]. A name on a card may refer to something already in the drawer, to a part that another card makes, or to something the workshop has no way of getting at all.

The drawer starts out holding the components named in stock. A card may be run whenever every name on its list is available, and the part it makes becomes available from then on. Availability is not used up: once a name is available, any number of cards may draw on it, in any order, as often as they like.

Return the names of all the parts the workshop can end up making. The names may be returned in any order.

Every name in builds and stock taken together is distinct, and no card lists the same name twice.

Examples

Example 1

Input
builds = ["cab", "roof", "seat"], needs = [["roof", "seat"], ["ply"], ["ply", "glue"]], stock = ["ply", "glue"]
Output
["roof", "seat", "cab"]

The drawer holds ply and glue, so the second and third cards can be run at once, and the two parts they make are exactly what the first card lists.

Example 2

Input
builds = ["boiler", "dome"], needs = [["dome"], ["boiler"]], stock = ["copper"]
Output
[]

The drawer holds only copper, and neither card lists copper, so neither card's list is met while the drawer stands as it is.

Example 3

Input
builds = ["smokebox", "buffer"], needs = [["steel", "rivet"], ["steel"]], stock = ["steel"]
Output
["buffer"]

The second card needs only steel, which is in the drawer. The first card also lists a rivet, a name that is neither in the drawer nor made by any card.

Example 4

Input
builds = ["lamp", "lens", "bulb"], needs = [["lens", "bulb"], ["glass"], ["filament", "lamp"]], stock = ["glass", "filament"]
Output
["lens"]

The lens card lists only glass, which is in the drawer, so it runs and the lens joins the available names. No other card's list is covered by glass, filament and the lens.

Constraints

  • n == builds.length == needs.length
  • 1 <= n <= 100
  • 1 <= needs[i].length, stock.length <= 100
  • 1 <= builds[i].length, needs[i][j].length, stock[k].length <= 10
  • builds[i], needs[i][j] and stock[k] consist only of lowercase English letters.
  • All the names in builds and stock combined are distinct.
  • No needs[i] contains a repeated name.

The values you return may be in any order.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_all_recipes(builds: list[str], needs: list[list[str]], stock: list[str]) -> list[str]:
Java
public List<String> findAllRecipes(String[] builds, List<List<String>> needs, String[] stock)

More on the same topics