从给定原材料中找到所有可以做出的菜

难度: 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" 。

示例 4：

输入：recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast"]
输出：[]
解释：
我们没法做出任何菜，因为我们只有原材料 "yeast" 。

提示：

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] 中的字符串互不相同。

Submission

运行时间: 92 ms

内存: 22.8 MB

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        # 1. build adjacency list for digraph, edge: recipe -> ingredient
        g = dict()
        for recipe, ingredient in zip(recipes, ingredients):
            g[recipe] = ingredient
        
        @lru_cache(maxsize=None)
        def dfs(recipe: str) -> bool:
            # base case 1: recipe is visited and backtracked
            if visited[recipe] == 2:
                return True 
            # base case 2: cycle exists
            if visited[recipe] == 1:
                return False
            # base case 3: recipe is in supply 
            if recipe in supplies:
                return True
            # base case 4: recipe is not in the recipes
            if recipe not in recipes:
                return False 
            # 若当前节点还未访问，访问
            visited[recipe] = 1      # 当前节点标记为已访问未回溯

            # 搜索邻接节点
            for ingredient in g[recipe]:
                if not dfs(ingredient):
                    return False 
                
            # backtracking
            visited[recipe] = 2    # 当前节点标记为已访问并回溯
            supplies.add(recipe)   # recipe can be created if we have all the ingredients for recipe
            return True 

        # 2. O(V+E) traverse the graph
        supplies = set(supplies)
        recipes = set(recipes)
        visited = defaultdict(int)   # 记录节点的访问状态  3种：0：未访问，1：已访问未回溯，2：已访问并回溯
        ans = []            
        
        for recipe in recipes:
            if dfs(recipe):
                ans.append(recipe)
        
        return ans

Explain

本题解使用深度优先搜索(DFS)和备忘录技术(lru_cache)来解决制作菜肴的问题。思路包括: 1. 使用图的表示方法，将每个菜肴作为节点，其原材料作为边连接。2. 对于每个菜肴，如果所有原材料都可以通过现有供应或者其他可制作的菜肴获得，则该菜肴可以被制作。 3. 使用DFS和回溯法检查每个菜肴是否可以制作，同时使用三种状态标记节点避免重复计算和检测环。 4. 通过递归深度优先搜索，如果一个菜肴的所有原料都可以获得，则这个菜肴标记为可制作，并添加到供应列表中，以供其他菜肴的原料检查使用。

时间复杂度: O(m+n)

空间复杂度: O(m+n)

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        # 构建菜肴的图表示: 菜肴到其原材料的映射
        g = dict()
        for recipe, ingredient in zip(recipes, ingredients):
            g[recipe] = ingredient
        
        # 使用lru_cache来缓存DFS结果，优化重复计算
        @lru_cache(maxsize=None)
        def dfs(recipe: str) -> bool:
            if visited[recipe] == 2: # 如果已经回溯过，直接返回True
                return True 
            if visited[recipe] == 1: # 如果在递归中再次遇到，表示有环
                return False
            if recipe in supplies: # 如果原材料已经在供应中，直接返回True
                return True
            if recipe not in recipes: # 如果不是一个菜肴，返回False
                return False 
            visited[recipe] = 1      # 标记为正在访问
            for ingredient in g[recipe]:
                if not dfs(ingredient):
                    return False 
            visited[recipe] = 2     # 标记为访问完毕
            supplies.add(recipe)   # 如果所有原材料都满足，将菜肴添加到供应中
            return True 
        supplies = set(supplies)
        recipes = set(recipes)
        visited = defaultdict(int)
        ans = []            
        for recipe in recipes:
            if dfs(recipe):
                ans.append(recipe)
        return ans

Explore

在题解的DFS实现中，为每个节点（即菜肴）维护三种状态：未访问（默认状态，无状态标记），正在访问（状态标记为1），和访问完毕（状态标记为2）。当DFS探索一个菜肴时，首先将其状态标记为“正在访问”。如果在这个状态下，我们再次遇到该菜肴（递归过程中），这表明存在一个循环依赖，即一个环。这时，算法会认定当前菜肴不能被制作（返回False）。只有当所有所需原材料的DFS探索都返回True，菜肴的状态才会被标记为“访问完毕”，并将菜肴添加到供应列表中。这种状态标记机制有效避免了算法进入无限循环。

在DFS算法中，三种状态具有以下作用及转换条件： 1. **未访问**：这是节点的初始状态，表示该节点尚未被DFS访问。 2. **正在访问**：当DFS开始探索一个节点时，该节点被标记为正在访问。这有助于检测环路：如果在探索过程中再次访问到标记为正在访问的节点，表示存在环，因而当前节点无法完成制作。 3. **访问完毕**：如果节点的所有依赖节点都能成功制作（即所有依赖的DFS调用返回True），节点状态更新为访问完毕。这表示该节点可以成功制作，并且此状态也帮助避免未来重复的DFS探索该节点，优化效率。状态的转换发生在DFS函数的控制流中：开始探索时标记为正在访问，探索结束后根据结果标记为访问完毕或回退到未访问状态（如果发现环或失败）。

lru_cache是一个缓存装饰器，它存储了最近调用的函数结果，并在后续调用中直接返回缓存的结果，而不是重新计算。在DFS中使用lru_cache可以显著提高效率，特别是在处理有重叠子问题的情况。在本题中，如果一个菜肴的制作依赖于其他菜肴，且这些菜肴的DFS结果已经被计算并缓存，那么lru_cache能够避免重复的DFS计算，直接使用缓存结果。这在有大量重复计算时（如多个菜肴共享相同的依赖）特别有用，可以显著减少总体的计算时间和资源消耗。