Dishes You Can Cook

Medium

A cookbook has len(dishes) dishes. To cook dishes[i] you need every ingredient listed in needs[i]. An ingredient may itself be another dish from the book, which then has to be cooked first. The pantry holds basic products, each in unlimited supply. A dish, once cooked, can also be used any number of times. Return every dish that can be cooked, in any order. Note that dishes may depend on each other in a loop; such dishes cannot be made.

Example 1

dishes=['dough', 'pizza', 'soup'], needs=[['flour', 'water'], ['dough', 'cheese'], ['beet', 'water']], pantry=['water', 'flour', 'cheese'] → ['dough', 'pizza']

Dough needs flour and water, and dough plus cheese gives pizza. Soup is impossible without beets.

Example 2

dishes=['jam', 'pie'], needs=[['pie'], ['jam', 'flour']], pantry=['flour', 'sugar'] → []

Jam needs pie and pie needs jam: a closed loop, so nothing can be made.

Example 3

dishes=['tea'], needs=[['leaves', 'water']], pantry=['water', 'leaves', 'milk'] → ['tea']

Everything for tea is in the pantry.

Constraints

1 ≤ len(dishes) = len(needs) ≤ 100
1 ≤ len(needs[i]), len(pantry) ≤ 100
every name is 1 to 20 characters: lowercase English letters and _
dish names and pantry items are all distinct
no needs[i] contains duplicates

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph Topological Sort Array Hash Table String

Similar problems

Expand a Template With Variables Medium Letter Order From a Dictionary Hard Tree Path Without Twin Neighbours Hard Letter Counts of Shortest Covers Hard Anagram Buckets Medium

Input

dishes=['dough', 'pizza', 'soup'], needs=[['flour', 'water'], ['dough', 'cheese'], ['beet', 'water']], pantry=['water', 'flour', 'cheese']

Expected

['dough', 'pizza']

Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.