aboutsummaryrefslogtreecommitdiff
path: root/word_subsets.c
diff options
context:
space:
mode:
Diffstat (limited to 'word_subsets.c')
-rw-r--r--word_subsets.c57
1 files changed, 57 insertions, 0 deletions
diff --git a/word_subsets.c b/word_subsets.c
new file mode 100644
index 0000000..72e7adf
--- /dev/null
+++ b/word_subsets.c
@@ -0,0 +1,57 @@
+// 916. Word Subsets
+#include "leetcode.h"
+
+/*
+ * you are given two string arrays 'words1' and 'words2'. a string 'b' is a
+ * subset of string 'a' if every letter in 'b' occurs in 'a' including
+ * multiplicity. a string 'a' from 'words1' is universal if for every string 'b'
+ * in 'words2', 'b' is a subset of 'a'. return an array of all the universal
+ * strins in 'words1'. you may return the answer in any order.
+ */
+
+char **wordSubsets(char **words1, int words1Size, char **words2, int words2Size,
+ int *returnSize) {
+ int max_freq[26] = {0}, tmp_freq[26];
+ for (int i = 0; i < words2Size; ++i) {
+ memset(tmp_freq, 0, sizeof(tmp_freq));
+ for (int j = 0; words2[i][j] != '\0'; ++j)
+ tmp_freq[words2[i][j] - 'a']++;
+ for (int j = 0; j < 26; ++j)
+ max_freq[j] = fmax(max_freq[j], tmp_freq[j]);
+ }
+ char **ans = (char **)malloc(words1Size * sizeof(char *));
+ *returnSize = 0;
+ for (int i = 0; i < words1Size; ++i) {
+ memset(tmp_freq, 0, sizeof(tmp_freq));
+ for (int j = 0; words1[i][j] != '\0'; ++j)
+ tmp_freq[words1[i][j] - 'a']++;
+ bool universal = true;
+ for (int j = 0; j < 26; ++j)
+ if (max_freq[j] > tmp_freq[j]) {
+ universal = false;
+ break;
+ }
+ if (universal)
+ ans[(*returnSize)++] = words1[i];
+ }
+ return ans;
+}
+
+int main() {
+ char *w11[] = {"amazon", "apple", "facebook", "google", "leetcode"},
+ *w21[] = {"e", "o"};
+ char *w12[] = {"amazon", "apple", "facebook", "google", "leetcode"},
+ *w22[] = {"l", "e"};
+ int rs1, rs2;
+ char **ws1 = wordSubsets((char **)w11, ARRAY_SIZE(w11), (char **)w21,
+ ARRAY_SIZE(w21), &rs1);
+ char **ws2 = wordSubsets((char **)w12, ARRAY_SIZE(w12), (char **)w22,
+ ARRAY_SIZE(w22), &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%s ", ws1[i]); // expect: ["facebook","google","leetcode"]
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%s ", ws2[i]); // expect: ["apple","google","leetcode"]
+ printf("\n");
+ free(ws1), free(ws2);
+}