aboutsummaryrefslogtreecommitdiff
path: root/possible_recipes_supplies.c
diff options
context:
space:
mode:
Diffstat (limited to 'possible_recipes_supplies.c')
-rw-r--r--possible_recipes_supplies.c128
1 files changed, 128 insertions, 0 deletions
diff --git a/possible_recipes_supplies.c b/possible_recipes_supplies.c
new file mode 100644
index 0000000..1761eaf
--- /dev/null
+++ b/possible_recipes_supplies.c
@@ -0,0 +1,128 @@
+// 2115. Find All Possible Recipes from Given Supplies
+#include "leetcode.h"
+
+/*
+ * you have information about 'n' different recipes. you are given a string
+ * array 'recipes' and a 2d string array 'ingredients'. the i'th recipe has the
+ * name 'recipes[i]', and you can create it is you have all the needed
+ * ingredients from 'ingredients[i]'. ingredients to a recipe may need to be
+ * created from other recipes, ie. '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.
+ */
+
+struct item {
+ struct item *next[26];
+ bool end;
+};
+
+struct item trie;
+
+void trie_init(void) { memset((void *)&trie, 0, sizeof(trie)); }
+
+void trie_push(char *s) {
+ struct item *header = ≜
+ for (int i = 0; s[i]; i++) {
+ if (!header->next[s[i] - 'a'])
+ header->next[s[i] - 'a'] = (struct item *)calloc(1, sizeof(struct item));
+ header = header->next[s[i] - 'a'];
+ }
+ header->end = true;
+}
+
+bool trie_find(char *s) {
+ struct item *header = ≜
+ for (int i = 0; s[i]; i++) {
+ if (!header->next[s[i] - 'a'])
+ return false;
+ header = header->next[s[i] - 'a'];
+ }
+ return header->end;
+}
+
+void trie_free_single(struct item *trie) {
+ if (trie) {
+ for (int i = 0; i < 26; i++)
+ trie_free_single(trie->next[i]);
+ free(trie);
+ }
+}
+
+void trie_free(void) {
+ for (int i = 0; i < 26; i++)
+ trie_free_single(trie.next[i]);
+}
+
+char **findAllRecipes(char **recipes, int recipesSize, char ***ingredients,
+ int ingredientsSize, int *ingredientsColSize,
+ char **supplies, int suppliesSize, int *returnSize) {
+ char **ans = (char **)malloc(recipesSize * sizeof(char *));
+ trie_init();
+ for (int i = 0; i < suppliesSize; i++)
+ trie_push(supplies[i]);
+ *returnSize = 0;
+ bool progress = true;
+ while (progress) {
+ progress = false;
+ for (int i = 0; i < recipesSize; i++) {
+ if (trie_find(recipes[i]))
+ continue;
+ bool create = true;
+ for (int j = 0; j < ingredientsColSize[i]; j++)
+ if (!trie_find(ingredients[i][j])) {
+ create = false;
+ break;
+ }
+ if (create) {
+ progress = true;
+ trie_push(recipes[i]);
+ ans[*returnSize] =
+ (char *)malloc((strlen(recipes[i]) + 1) * sizeof(char));
+ strcpy(ans[*returnSize], recipes[i]);
+ (*returnSize)++;
+ }
+ }
+ }
+ trie_free();
+ return ans;
+}
+
+int main() {
+ char *r1[] = {"bread"};
+ char *i11[] = {"yeast", "flour"};
+ char **i1 = {i11};
+ char *s1[] = {"yeast", "flour", "corn"};
+ char *r2[] = {"bread", "sandwich"};
+ char *i21[] = {"yeast", "flour"}, *i22[] = {"bread", "meat"};
+ char **i2[] = {i21, i22};
+ char *s2[] = {"yeast", "flour", "meat"};
+ char *r3[] = {"bread", "sandwich", "burger"};
+ char *i31[] = {"yeast", "flour"}, *i32[] = {"bread", "meat"},
+ *i33[] = {"sandwich", "meat", "bread"};
+ char **i3[] = {i31, i32, i33};
+ char *s3[] = {"yeast", "flour", "meat"};
+ int rs1, rs2, rs3;
+ char **far1 =
+ findAllRecipes(r1, ARRAY_SIZE(r1), (char ***)i1, ARRAY_SIZE(i11),
+ (int *)ARRAY_SIZE(i11), s1, ARRAY_SIZE(s1), &rs1);
+ char **far2 =
+ findAllRecipes(r2, ARRAY_SIZE(r2), (char ***)i2, ARRAY_SIZE(i21),
+ (int *)ARRAY_SIZE(i21), s2, ARRAY_SIZE(s2), &rs2);
+ char **far3 =
+ findAllRecipes(r3, ARRAY_SIZE(r3), (char ***)i3, ARRAY_SIZE(i31),
+ (int *)ARRAY_SIZE(i31), s3, ARRAY_SIZE(s3), &rs3);
+ for (int i = 0; i < rs1; i++)
+ printf("%s ", far1[i]); // expect: ["bread"]
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%s ", far2[i]); // expect: ["bread","sandwich"]
+ printf("\n");
+ for (int i = 0; i < rs3; i++)
+ printf("%s ", far3[i]); // expect: ["bread","sandwich","burger"]
+ printf("\n");
+ free(far1);
+ free(far2);
+ free(far3);
+}