diff options
author | Jack Sangdahl <[email protected]> | 2025-01-10 09:46:39 +0100 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-10 09:46:39 +0100 |
commit | 3698398d290bdb4c94bd13046d16d96713b8111b (patch) | |
tree | 036ad09f003760882fe198ee0ce3b2da3c5f030c | |
parent | 8050c7264ba4487a1e64b150633961097382ac5b (diff) | |
download | leetcode-3698398d290bdb4c94bd13046d16d96713b8111b.tar.gz leetcode-3698398d290bdb4c94bd13046d16d96713b8111b.zip |
916. word subsets
-rw-r--r-- | word_subsets.c | 57 | ||||
-rw-r--r-- | word_subsets.cpp | 69 | ||||
-rw-r--r-- | word_subsets.py | 39 |
3 files changed, 142 insertions, 23 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); +} diff --git a/word_subsets.cpp b/word_subsets.cpp index ea4c1f9..d053375 100644 --- a/word_subsets.cpp +++ b/word_subsets.cpp @@ -1,34 +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. + */ + class Solution { public: vector<string> wordSubsets(vector<string> &words1, vector<string> &words2) { - int bFreq[26] = {0}, check[26] = {0}; - int cMax = 0; - vector<string> ans; - for (string word : words2) { - for (char c : word) - check[c - 'a']++; - for (int j = 0; j < 26; j++) { - int diff = check[j] - bFreq[j]; - if (diff > 0) - cMax += diff, bFreq[j] += diff; - } - if (cMax > 10) - return ans; - fill(check, check + 26, 0); + vector<int> cnt(26), tmp(26); + int i; + for (string b : words2) { + tmp = counter(b); + for (i = 0; i < 26; ++i) + cnt[i] = max(cnt[i], tmp[i]); } - for (string word : words1) { - int j; - for (char c : word) - check[c - 'a']++; - for (j = 0; j < 26; j++) - if (check[j] < bFreq[j]) + vector<string> ans; + for (string a : words1) { + tmp = counter(a); + for (i = 0; i < 26; ++i) + if (tmp[i] < cnt[i]) break; - if (j == 26) - ans.push_back(word); - fill(check, check + 26, 0); + if (i == 26) + ans.push_back(a); } return ans; } + +private: + vector<int> counter(string &word) { + vector<int> cnt(26); + for (char c : word) + cnt[c - 'a']++; + return cnt; + } }; + +int main() { + Solution obj; + vector<string> w11 = {"amazon", "apple", "facebook", "google", "leetcode"}, + w21 = {"e", "o"}; + vector<string> w12 = {"amazon", "apple", "facebook", "google", "leetcode"}, + w22 = {"l", "e"}; + vector<string> ws1 = obj.wordSubsets(w11, w21), + ws2 = obj.wordSubsets(w12, w22); + for (auto i : ws1) + cout << i << ' '; // expect: ["facebook","google","leetcode"] + printf("\n"); + for (auto i : ws2) + cout << i << ' '; // expect: ["apple","google","leetcode"] + printf("\n"); +} diff --git a/word_subsets.py b/word_subsets.py new file mode 100644 index 0000000..dac7b6a --- /dev/null +++ b/word_subsets.py @@ -0,0 +1,39 @@ +# 916. Word Subsets +from collections import Counter +from functools import reduce +import operator + +""" +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. +""" + + +class Solution(object): + def wordSubsets(self, words1, words2): + """ + :type words1: List[str] + :type words2: List[str] + :rtype: List[str] + """ + c_b = reduce(operator.or_, (Counter(w) for w in words2)) + return [a for a in words1 if c_b & Counter(a) == c_b] + + +if __name__ == "__main__": + obj = Solution() + print( + obj.wordSubsets( + words1=["amazon", "apple", "facebook", "google", "leetcode"], + words2=["e", "o"], + ) + ) + print( + obj.wordSubsets( + words1=["amazon", "apple", "facebook", "google", "leetcode"], + words2=["l", "e"], + ) + ) |