Leetcode 2115. Find All Possible Recipes from Given Supplies

Jimmy   Mar 21, 2025   499 words   ~15 mins
#Array #Hash Table #String #Graph #Topological Sort

Table of Contents

題目資訊

題目敘述

你有關於 $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 \leq n \leq 100$
  • $1 \leq ingredients[i].length, supplies.length \leq 100$
  • $1 \leq recipes[i].length, ingredients[i][j].length, supplies[k].length \leq 10$
  • recipes[i]、ingredients[i][j] 和 supplies[k] 僅由小寫英文字母組成。
  • recipes 和 supplies 的所有值加起來是唯一的。
  • 每個 ingredients[i] 不包含任何重複的值。

直覺

這個問題的核心在於確定哪些食譜可以根據給定的食譜列表、所需的食材以及初始的供應來製作。一些食譜可以作為其他食譜的食材，從而形成依賴鏈。因此，可以將此問題視為圖遍歷，圖中的節點表示食譜，而邊表示食材依賴。主要挑戰在於確保食譜的所有依賴項都可以直接透過初始供應滿足或間接通過其他可創建的食譜滿足。

解法

這個解法採用了動態規劃方法並結合圖遍歷技術來有效地確定哪些食譜可以被製作。整體策略包括以下步驟：

  1. 資料結構初始化：

    • 使用 set 來維護 availableSupplies，其中包括所有初始可用的食材。
    • 使用 map (recipeIndexMap) 來將每個食譜與其索引相關聯，以便快速查找。
    • 使用 vector (dp) 進行記憶化，以存儲每個食譜的計算結果。dp 中的每個條目可以是 -1（未訪問）、0（無法製作食譜）或 1（可以製作食譜）。

  2. 將食譜映射到索引：

    • 遍歷所有食譜並填充 recipeIndexMap，以便更容易地獲取食譜在 recipes 列表中的索引。

  3. 使用帶記憶化的深度優先搜索檢查可創建的食譜：

    • 對於每個食譜，調用輔助函數 canMakeRecipe() 檢查該食譜是否可以被創建。
    • 在 canMakeRecipe() 中使用記憶化來避免重新計算已被檢查過的食譜結果。
    • 對於食譜要求的每個食材：
      • 如果該食材不在 availableSupplies 中，且根據之前的計算不是可創建的食譜，則標記該食譜為不可創建 (dp[index] = 0)，並返回 false。
    • 如果一個食譜的所有食材均被滿足，則將其標記為可創建 (dp[index] = 1) 並返回 true。

  4. 收集可創建的食譜：

    • 遍歷 recipes 列表，對於每個食譜，使用 canMakeRecipe() 的結果來確定其是否可以添加到 creatableRecipes 列表中。

通過遵循此方法，演算法確保每個食譜都被有效地處理，包含直接供應和通過其他食譜的可能遞歸依賴。這一方法有效地解決了在給定的食材和供應限制下動態確定可創建食譜的問題。

程式碼

C++

class Solution {
public:
    // 輔助函數來判斷一個食譜是否可以被製作
    bool canMakeRecipe(
        int index, 
        vector<string>& recipes, 
        vector<vector<string>>& ingredients, 
        set<string>& availableSupplies, 
        vector<int>& dp, 
        map<string, int>& recipeIndexMap
    ) {
        // 記憶化檢查結果是否已經計算過
        if (dp[index] != -1) 
            return dp[index];

        // 初始化為失敗狀態
        dp[index] = 0;

        // 檢查所有的食材是否可用或可以被製作
        for (string ingredient : ingredients[index]) {
            // 如果食材既不是供應品也不是可製作的食譜
            if (availableSupplies.count(ingredient) == 0 && 
                (recipeIndexMap.find(ingredient) == recipeIndexMap.end() || 
                 !canMakeRecipe(recipeIndexMap[ingredient], recipes, ingredients, availableSupplies, dp, recipeIndexMap))) 
                return dp[index] = 0; // 無法製作食譜
        }

        // 所有食材都可用，食譜可以被製作
        return dp[index] = 1;
    }

    // 主函數用於找出所有可被製作的食譜
    vector<string> findAllRecipes(
        vector<string>& recipes, 
        vector<vector<string>>& ingredients, 
        vector<string>& supplies
    ) {
        set<string> availableSupplies(supplies.begin(), supplies.end()); // 初始可用供應品的集合
        map<string, int> recipeIndexMap; // 將食譜名稱映射至其索引
        vector<string> creatableRecipes; // 用於儲存可被製作的食譜列表
        vector<int> dp(recipes.size(), -1); // 記憶化向量 (-1: 未訪問, 0: 無法製作, 1: 可以製作)

        // 將每個食譜映射至相應的索引
        for (int i = 0; i < recipes.size(); i++)
            recipeIndexMap[recipes[i]] = i;

        // 檢查每個食譜是否可以被製作
        for (int i = 0; i < recipes.size(); i++) {
            if (canMakeRecipe(i, recipes, ingredients, availableSupplies, dp, recipeIndexMap))
                creatableRecipes.push_back(recipes[i]);
        }

        return creatableRecipes; // 返回所有可以被製作的食譜
    }
};

Python

class Solution:
    # 輔助函數，用於判斷一個食譜是否可被製作
    def canMakeRecipe(
        self, 
        index, 
        recipes, 
        ingredients, 
        availableSupplies, 
        dp, 
        recipeIndexMap
    ):
        # 記憶化檢查結果是否已經計算過
        if dp[index] != -1:
            return dp[index]

        # 初始狀態設為失敗
        dp[index] = 0

        # 檢查是否所有食材都可供應或可被製作
        for ingredient in ingredients[index]:
            # 如果食材不是原料也不是可被製作的食譜
            if (ingredient not in availableSupplies and 
                (ingredient not in recipeIndexMap or 
                 not self.canMakeRecipe(recipeIndexMap[ingredient], recipes, ingredients, availableSupplies, dp, recipeIndexMap))):
                return dp[index]  # 無法製作該食譜

        # 所有食材均可供應，食譜可以被製作
        dp[index] = 1
        return dp[index]

    # 主函數，用於查找所有可被製作的食譜
    def findAllRecipes(self, recipes, ingredients, supplies):
        availableSupplies = set(supplies)  # 初始可用食材的集合
        recipeIndexMap = {}  # 將食譜名稱映射到其索引
        creatableRecipes = []  # 用於存儲可被製作的食譜列表
        dp = [-1] * len(recipes)  # 記憶化向量 (-1: 未訪問, 0: 無法製作, 1: 可以製作)

        # 將每個食譜映射到其對應的索引
        for i in range(len(recipes)):
            recipeIndexMap[recipes[i]] = i

        # 檢查每個食譜是否可以被製作
        for i in range(len(recipes)):
            if self.canMakeRecipe(i, recipes, ingredients, availableSupplies, dp, recipeIndexMap):
                creatableRecipes.append(recipes[i])

        return creatableRecipes  # 返回所有可被製作的食譜列表

複雜度分析

  • 時間複雜度: $O(|R| \cdot |I|)$，其中 $|R|$ 是食譜的數量，$|I|$ 是一個食譜中最大數量的成分。canMakeRecipe 函數通過遍歷每個食譜的成分來運行，並在遞迴過程中遞迴檢查可創建的成分。這形成了一個食譜圖上的深度優先搜索 (DFS)。由於每次 canMakeRecipe 的呼叫都備忘錄化，每個食譜基於其直接和傳遞的依賴關係被檢查的次數是有限的，從而導致食譜和成分的線性關係。遍歷所有食譜進一步將此乘以上述食譜的數量。

  • 空間複雜度: $O(|R| + |S|)$，其中 $|R|$ 是食譜的數量，$|S|$ 是初始供應的數量。這考慮到將可用供應存儲在集合中及 dp 陣列的備忘錄狀態。函數中使用的每個映射和集合都需要與存儲元素數量成比例的空間，即食譜和供應品。遞迴調用堆疊也可能對空間使用有貢獻，但這主要受限於這些主要的存儲結構。

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.