1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
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);
}
|