You have information about n
different recipes. You are given a string array recipes
and a 2D string array ingredients
. The ith
recipe has the name recipes[i]
, and you can create it if you have all the needed ingredients from ingredients[i]
. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i]
may contain a string that is in recipes
.
You are also given a string array supplies
containing all the ingredients that you initially have, and you have an infinite supply of all of them.
Return a list of all the recipes that you can create. You may return the answer in any order.
Note that two recipes may contain each other in their ingredients.
Example 1:
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".
Example 2:
Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"] Output: ["bread","sandwich"] Explanation: We can create "bread" since we have the ingredients "yeast" and "flour". We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
Example 3:
Input: recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"] Output: ["bread","sandwich","burger"] Explanation: We can create "bread" since we have the ingredients "yeast" and "flour". We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread". We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".
Constraints:
n == recipes.length == ingredients.length
1 <= n <= 100
1 <= ingredients[i].length, supplies.length <= 100
1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10
recipes[i], ingredients[i][j]
, andsupplies[k]
consist only of lowercase English letters.- All the values of
recipes
andsupplies
combined are unique. - Each
ingredients[i]
does not contain any duplicate values.
Solution: Brute Force
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua class Solution { public: vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) { const int n = recipes.size(); unordered_set<string> s(begin(supplies), end(supplies)); vector<string> ans; vector<int> seen(n); while (true) { bool newSupply = false; for (int i = 0; i < n; ++i) { if (seen[i]) continue; bool hasAll = true; for (const string& ingredient : ingredients[i]) if (!s.count(ingredient)) { hasAll = false; break; } if (!hasAll) continue; ans.push_back(recipes[i]); seen[i] = 1; s.insert(recipes[i]); newSupply = true; } if (!newSupply) break; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment