LeetCode每日一题(2115. Find All Possible Recipes from Given Supplies)

You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes.

You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.

Return a list of all the recipes that you can create. You may return the answer in any order.

Note that two recipes may contain each other in their ingredients.

Example 1:

Input: recipes = [“bread”], ingredients = [[“yeast”,“flour”]], supplies = [“yeast”,“flour”,“corn”]
Output: [“bread”]

Explanation:
We can create “bread” since we have the ingredients “yeast” and “flour”.

Example 2:

Input: recipes = [“bread”,“sandwich”], ingredients = [[“yeast”,“flour”],[“bread”,“meat”]], supplies = [“yeast”,“flour”,“meat”]
Output: [“bread”,“sandwich”]

Explanation:
We can create “bread” since we have the ingredients “yeast” and “flour”.
We can create “sandwich” since we have the ingredient “meat” and can create the ingredient “bread”.
Example 3:

Input: recipes = [“bread”,“sandwich”,“burger”], ingredients = [[“yeast”,“flour”],[“bread”,“meat”],[“sandwich”,“meat”,“bread”]], supplies = [“yeast”,“flour”,“meat”]
Output: [“bread”,“sandwich”,“burger”]

Explanation:
We can create “bread” since we have the ingredients “yeast” and “flour”.
We can create “sandwich” since we have the ingredient “meat” and can create the ingredient “bread”.
We can create “burger” since we have the ingredient “meat” and can create the ingredients “bread” and “sandwich”.

Constraints:

• 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], and supplies[k] consist only of lowercase English letters.
• All the values of recipes and supplies combined are unique.
• Each ingredients[i] does not contain any duplicate values.

---

菜谱里面居然会出现会出现死循环， 我要做面包，需要面粉与奶油，但是面粉又需要面包来做，这感觉不像菜谱，更像经济学， 我们为工人提供面包才能产出面粉, 应该是这个意思。

抛开这些不太符合逻辑的问题不谈， 其实这就是一个路径查找问题， 我们吧 supplies 作为所有叶子节点的集合， 只要一个 recipe 中所有的 ingredients 都在 supplies 中出现了， 我们就认为我们可以做这种食物。如果 recipe 中的某种 ingredient 没有出现在 supplies 中， 那有两种可能， 一种是该 ingredient 本身也是一个 recipe, 并且我们还没有检查它是否能做得出来。另一种情况就是我们确实没有这种原料, 我们没法做成该食物。

---

use std::collections::{
    HashMap, HashSet};

impl Solution {
    
    fn find(
        recipes: &HashMap<String, HashSet<String>>,
        key: &str,
        cache: &mut HashMap<String, bool>,
        mut visited: HashSet<String>,
    ) -> bool {
    
        visited.insert(key.to_owned());
        if let Some(ok) = cache.get(key) {
    
            return *ok;
        }
        if let Some(igds) = recipes.get(key) {
    
            for igd in igds {
    
                if visited.contains(igd) {
    
                    return false;
                }
                if let Some(igd) = cache.get(igd) {
    
                    if !(*igd) {
    
                        cache.insert(key.to_owned(), false);
                        return false;
                    }
                    continue;
                }
                if !Solution::find(recipes, igd, cache, visited.clone()) {
    
                    cache.insert(key.to_owned(), false);
                    return false;
                }
            }
            cache.insert(key.to_owned(), true);
            return true;
        }
        cache.insert(key.to_owned(), false);
        false
    }
    pub fn find_all_recipes(
        recipes: Vec<String>,
        ingredients: Vec<Vec<String>>,
        supplies: Vec<String>,
    ) -> Vec<String> {
    
        let mut rc = HashMap::new();
        for (r, igds) in recipes.clone().into_iter().zip(ingredients) {
    
            let set: HashSet<String> = igds.into_iter().collect();
            rc.insert(r, set);
        }
        let mut cache: HashMap<String, bool> = supplies.into_iter().map(|v| (v, true)).collect();
        let mut ans = Vec::new();
        for r in recipes {
    
            if Solution::find(&rc, &r, &mut cache, HashSet::new()) {
    
                ans.push(r);
            }
        }
        ans
    }
}