题目描述

给定一个字符串数组 recipes（食谱）、一个二维字符串数组 ingredients（每个食谱所需的食材列表）以及一个字符串数组 supplies（当前拥有的所有食材）。每道菜做好后也可以作为其他菜的食材。返回所有可以做出的食谱列表。

解题方法

思路分析

本题的核心在于处理食谱与食材之间的依赖关系。一道菜依赖若干种食材，而做好的菜又可以作为其他菜的食材，这种"前置条件满足后才能解锁"的特性决定了可以使用拓扑排序来解决。

将每种食材和食谱都看作图上的节点，从食材向需要它的食谱连有向边，同时记录每个食谱的入度（即所需食材的种类数）。初始时，所有 supplies 中的食材都是可用的，将它们作为 BFS 的起点。每当一个食谱的所有前置食材都备齐（入度减为 0），该食谱便可被做出，并作为新的可用节点去解锁更多食谱。

算法步骤

  1. 建图与初始化入度：遍历每个食谱，将其每种食材与食谱建立有向边，并记录每个食谱的入度。
  2. BFS 拓扑遍历：将已有食材入队，依次出队并减少依赖它的食谱的入度，当某个食谱入度为 0 时将其入队并加入答案。
  3. 返回结果：所有能做出的食谱即为答案。

代码注释与解析

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:
                # 建立连接：从食材 s 指向食谱 r
                g[s].append(r)
            # 初始化该食谱的入度 = 所需食材数量
            deg[r] = len(ing)

        ans = []
        # 原料是不需要先前条件的，直接作为 BFS 起点
        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

代码要点说明

  • 邻接表 g：以食材/食谱为键，值为依赖该食材的食谱列表，实现了从食材到食谱的快速查找。
  • 入度表 deg：记录每个食谱当前尚未满足的食材种类数，初始值为食谱所需的食材总数。
  • 队列 q：存储当前可用的所有资源（包括初始原料和已做出的菜），是整个拓扑排序的驱动核心。
  • BFS 过程：每次从队列中取出一个可用资源，将其所有出边的目标节点（食谱）的入度减 1，当入度归零时意味着该食谱可以做出。

复杂度分析

  • 时间复杂度：O(N + M)，其中 N 为食谱数量，M 为所有食谱的食材总数（即 ingredients 中所有子数组的长度之和）。建图需遍历所有食材，BFS 中每条有向边恰好被处理一次。
  • 空间复杂度：O(N + M)，邻接表 g 存储 M 条边，入度表 deg 存储 N 个食谱的入度，队列 q 最多存储 N 个元素。