class Solution {
public:
vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
}
};
2115. 从给定原材料中找到所有可以做出的菜
你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] ，如果你有它 所有 的原材料 ingredients[i] ，那么你可以 做出 这道菜。一道菜的原材料可能是 另一道 菜，也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。
同时给你一个字符串数组 supplies ，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。
请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。
注意两道菜在它们的原材料中可能互相包含。
示例 1：
输入：recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"] 输出：["bread"] 解释： 我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。
示例 2：
输入：recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"] 输出：["bread","sandwich"] 解释： 我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。 我们可以做出 "sandwich" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 。
示例 3：
输入：recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"] 输出：["bread","sandwich","burger"] 解释： 我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。 我们可以做出 "sandwich" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 。 我们可以做出 "burger" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 和 "sandwich" 。
示例 4：
输入：recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast"] 输出：[] 解释： 我们没法做出任何菜，因为我们只有原材料 "yeast" 。
提示：
n == recipes.length == ingredients.length1 <= n <= 1001 <= ingredients[i].length, supplies.length <= 1001 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10recipes[i], ingredients[i][j] 和 supplies[k] 只包含小写英文字母。recipes 和 supplies 中的值互不相同。ingredients[i] 中的字符串互不相同。原站题解
java 解法, 执行用时: 84 ms, 内存消耗: 44.3 MB, 提交时间: 2023-09-23 11:11:54
class Solution {
// topological sort + bfs
public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
// build graph
Map<String, List<String>> map = new HashMap<>();
Map<String, Integer> indegree = new HashMap<>();
int n = recipes.length;
for(int i = 0; i < n; i++) {
for(String s : ingredients.get(i)) {
if(!map.containsKey(s)) {
map.put(s, new ArrayList<>());
}
map.get(s).add(recipes[i]);
indegree.put(recipes[i], indegree.getOrDefault(recipes[i], 0) + 1);
}
}
Deque<String> queue = new ArrayDeque<>();
for(int i = 0; i < supplies.length; i++) {
queue.offer(supplies[i]);
}
// bfs
while(!queue.isEmpty()) {
int len = queue.size();
for(int i = 0; i < len; i++) {
String igd = queue.poll();
for(String neighb : map.getOrDefault(igd , new ArrayList<>())) {
// decrease correspond indegree
indegree.put(neighb, indegree.get(neighb) - 1);
if(indegree.get(neighb) == 0) {
queue.offer(neighb);
}
}
}
}
// extract in-degree == 0 's recipes in indegree map
List<String> ans = new ArrayList<>();
for(Map.Entry<String, Integer> entry : indegree.entrySet()) {
if(entry.getValue() == 0) {
ans.add(entry.getKey());
}
}
return ans;
}
}
python3 解法, 执行用时: 180 ms, 内存消耗: 18.9 MB, 提交时间: 2023-09-23 11:11:21
class Solution:
def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
n = len(recipes)
# 图
depend = defaultdict(list)
# 入度统计
cnt = Counter()
for i in range(n):
for ing in ingredients[i]:
depend[ing].append(recipes[i])
cnt[recipes[i]] = len(ingredients[i])
ans = list()
# 把初始的原材料放入队列
q = deque(supplies)
# 拓扑排序
while q:
cur = q.popleft()
if cur in depend:
for rec in depend[cur]:
cnt[rec] -= 1
# 如果入度变为 0，说明可以做出这道菜
if cnt[rec] == 0:
ans.append(rec)
q.append(rec)
return ans
cpp 解法, 执行用时: 380 ms, 内存消耗: 155.8 MB, 提交时间: 2023-09-23 11:10:50
class Solution {
public:
vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
unordered_map<string,vector<string>> table;
unordered_map<string,int> indegree;
int n=recipes.size();
for(int i=0;i<n;i++){
for(int j=0;j<ingredients[i].size();j++){
table[ingredients[i][j]].push_back(recipes[i]);
indegree[recipes[i]]++;
}
}
queue<string> q;
for(auto sup:supplies){
q.push(sup);
}
vector<string> res;
while(!q.empty()){
string tp=q.front();
q.pop();
for(auto &nxt:table[tp]){
if(--indegree[nxt]==0){
q.push(nxt);
res.push_back(nxt);
}
}
}
return res;
}
};
golang 解法, 执行用时: 152 ms, 内存消耗: 7.2 MB, 提交时间: 2023-09-23 11:10:36
func findAllRecipes(recipes []string, ingredients [][]string, q []string) (ans []string) {
g := map[string][]string{}
deg := make(map[string]int, len(recipes))
for i, r := range recipes {
for _, s := range ingredients[i] {
g[s] = append(g[s], r) // 从这道菜的原材料向这道菜连边
}
deg[r] = len(ingredients[i])
}
for len(q) > 0 { // 拓扑排序（这里我们直接用初始原材料当队列）
s := q[0]
q = q[1:]
for _, r := range g[s] {
if deg[r]--; deg[r] == 0 { // 这道菜的所有原材料我们都有
q = append(q, r)
ans = append(ans, r)
}
}
}
return
}
python3 解法, 执行用时: 168 ms, 内存消耗: 19 MB, 提交时间: 2023-09-23 11:10:21
class Solution:
def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
g = defaultdict(list)
deg = {}
for r, ing in zip(recipes, ingredients):
for s in ing:
g[s].append(r) # 从这道菜的原材料向这道菜连边
deg[r] = len(ing)
ans = []
q = deque(supplies) # 拓扑排序（用初始原材料当队列）
while q:
for r in g[q.popleft()]:
deg[r] -= 1
if deg[r] == 0: # 这道菜的所有原材料我们都有
q.append(r)
ans.append(r)
return ans