Medium

题目描述

你有 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"。

约束条件：

  • 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] 和 supplies[k] 只包含小写英文字母
  • recipes 和 supplies 合并后的所有值都是唯一的
  • 每个 ingredients[i] 不包含任何重复值

解题思路

这是一个经典的拓扑排序问题。我们需要找到所有可以制作的食谱，其中食谱之间可能存在依赖关系。

核心思路：

  1. 建图：将食谱和原料之间的依赖关系建模为有向图。每个食谱指向它所需的原料，如果原料本身也是食谱，则形成依赖链。

  2. 拓扑排序：使用拓扑排序来确定制作顺序。我们维护每个食谱的入度（需要的原料数量），当某个食谱的所有原料都可获得时，该食谱就可以制作。

  3. 动态更新：当我们制作出一个新食谱时，它可以作为其他食谱的原料，因此需要更新相关食谱的入度。

算法步骤：

  • 初始化可用原料集合（包含初始supplies）
  • 为每个食谱计算入度（所需且当前不可用的原料数量）
  • 使用队列处理入度为0的食谱（可以立即制作的）
  • 每制作一个食谱，就将其加入可用原料，并更新其他食谱的入度
  • 重复直到没有新的食谱可以制作

这种方法确保我们按正确的依赖顺序制作食谱，时间复杂度为O(V + E)，其中V是食谱数量，E是依赖关系数量。

代码实现

class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        unordered_set<string> available(supplies.begin(), supplies.end());
        unordered_map<string, int> indegree;
        unordered_map<string, vector<string>> graph;
        
        // 初始化入度
        for (int i = 0; i < recipes.size(); i++) {
            string recipe = recipes[i];
            for (const string& ingredient : ingredients[i]) {
                if (available.find(ingredient) == available.end()) {
                    indegree[recipe]++;
                    graph[ingredient].push_back(recipe);
                }
            }
        }
        
        // 找到入度为0的食谱
        queue<string> q;
        for (const string& recipe : recipes) {
            if (indegree[recipe] == 0) {
                q.push(recipe);
            }
        }
        
        vector<string> result;
        while (!q.empty()) {
            string recipe = q.front();
            q.pop();
            result.push_back(recipe);
            available.insert(recipe);
            
            // 更新依赖此食谱的其他食谱的入度
            for (const string& nextRecipe : graph[recipe]) {
                indegree[nextRecipe]--;
                if (indegree[nextRecipe] == 0) {
                    q.push(nextRecipe);
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        available = set(supplies)
        indegree = defaultdict(int)
        graph = defaultdict(list)
        
        # 计算入度和建图
        for i, recipe in enumerate(recipes):
            for ingredient in ingredients[i]:
                if ingredient not in available:
                    indegree[recipe] += 1
                    graph[ingredient].append(recipe)
        
        # 找到入度为0的食谱
        queue = deque()
        for recipe in recipes:
            if indegree[recipe] == 0:
                queue.append(recipe)
        
        result = []
        while queue:
            recipe = queue.popleft()
            result.append(recipe)
            available.add(recipe)
            
            # 更新依赖此食谱的其他食谱的入度
            for next_recipe in graph[recipe]:
                indegree[next_recipe] -= 1
                if indegree[next_recipe] == 0:
                    queue.append(next_recipe)
        
        return result

public class Solution {
    public IList<string> FindAllRecipes(string[] recipes, IList<IList<string>> ingredients, string[] supplies) {
        var available = new HashSet<string>(supplies);
        var indegree = new Dictionary<string, int>();
        var graph = new Dictionary<string, List<string>>();
        
        // 初始化入度和建图
        for (int i = 0; i < recipes.Length; i++) {
            string recipe = recipes[i];
            indegree[recipe] = 0;
            foreach (string ingredient in ingredients[i]) {
                if (!available.Contains(ingredient)) {
                    indegree[recipe]++;
                    if (!graph.ContainsKey(ingredient)) {
                        graph[ingredient] = new List<string>();
                    }
                    graph[ingredient].Add(recipe);
                }
            }
        }
        
        // 找到入度为0的食谱
        var queue = new Queue<string>();
        foreach (string recipe in recipes) {
            if (indegree[recipe] == 0) {
                queue.Enqueue(recipe);
            }
        }
        
        var result = new List<string>();
        while (queue.Count > 0) {
            string recipe = queue.Dequeue();
            result.Add(recipe);
            available.Add(recipe);
            
            // 更新依赖此食谱的其他食谱的入度
            if (graph.ContainsKey(recipe)) {
                foreach (string nextRecipe in graph[recipe]) {
                    indegree[nextRecipe]--;
                    if (indegree[nextRecipe] == 0) {
                        queue.Enqueue(nextRecipe);
                    }
                }
            }
        }
        
        return result;
    }
}

var findAllRecipes = function(recipes, ingredients, supplies) {
    const available = new Set(supplies);
    const recipeMap = new Map();
    
    for (let i = 0; i < recipes.length; i++) {
        recipeMap.set(recipes[i], ingredients[i]);
    }
    
    const result = [];
    const visited = new Set();
    const inProgress = new Set();
    
    function canMake(recipe) {
        if (available.has(recipe)) return true;
        if (visited.has(recipe)) return false;
        if (inProgress.has(recipe)) return false;
        if (!recipeMap.has(recipe)) return false;
        
        inProgress.add(recipe);
        
        for (const ingredient of recipeMap.get(recipe)) {
            if (!canMake(ingredient)) {
                inProgress.delete(recipe);
                visited.add(recipe);
                return false;
            }
        }
        
        inProgress.delete(recipe);
        available.add(recipe);
        result.push(recipe);
        return true;
    }
    
    for (const recipe of recipes) {
        canMake(recipe);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(V + E)V为食谱数量，E为依赖关系总数（所有原料的总和）
空间复杂度O(V + E)存储图结构、入度信息和可用原料集合

相关题目