Algorithm
Problem Name: 916. Word Subsets
Problem Link: https://leetcode.com/problems/word-subsets/
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.
- For example,
"wrr"is a subset of"warrior"but is not a subset of"world".
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 strings in words1. You may return the answer in any order.
Example 1:
Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"] Output: ["facebook","google","leetcode"]
Example 2:
Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"] Output: ["apple","google","leetcode"]
Constraints:
1 <= words1.length, words2.length <= 1041 <= words1[i].length, words2[i].length <= 10words1[i]andwords2[i]consist only of lowercase English letters.- All the strings of
words1are unique.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
vector<string>res;
vector<int>maxCount(26);
for (int i = 0; i < B.size(); ++i) {
vector<int> v = getCount(B[i]);
for (int j = 0; j < 26; ++j) {
maxCount[j] = max(maxCount[j], v[j]);
}
}
for (int i = 0; i < A.size(); ++i) {
vector<int> v = getCount(A[i]);
bool isValid(true);
for (int j = 0; j < 26; ++j) {
if (v[j] < maxCount[j]) {
isValid = false;
break;
}
}
if (isValid) {
res.push_back(A[i]);
}
}
return res;
}
vector<int> getCount(string& s) {
vector<int>cnt(26);
for (int i = 0; i < s.size(); ++i) {
cnt[s[i] - 'a']++;
}
return cnt;
}
};
Input
words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output
["facebook","google","leetcode"]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List wordSubsets(String[] words1, String[] words2) {
int[] word2MaxCount = new int[26];
for (String word : words2) {
int[] count = getFrequencyArray(word);
for (int i = 0; i < 26; i++) {
word2MaxCount[i] = Math.max(word2MaxCount[i], count[i]);
}
}
List < String> result = new ArrayList<>();
for (String word : words1) {
int[] count = getFrequencyArray(word);
for (int i = 0; i < 26; i++) {
if (count[i] < word2MaxCount[i]) {
break;
}
if (i == 25) {
result.add(word);
}
}
}
return result;
}
private static int[] getFrequencyArray(String s) {
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
return count;
}
}
Input
words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output
["facebook","google","leetcode"]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const wordSubsets = function(A, B) {
function counter(s) {
let count = Array(26).fill(0);
for (let i = 0; i < s.length; i++) count[s.charCodeAt(i) - 97]++;
return count;
}
let aux = Array(26).fill(0);
let result = [];
for (let i = 0; i < B.length; i++) {
let count = counter(B[i]);
for (let i = 0; i < 26; i++) {
aux[i] = Math.max(aux[i], count[i]);
}
}
for (let i = 0; i < A.length; i++) {
let count = counter(A[i]);
let flag = true;
for (let j = 0; j < 26; j++) {
if (aux[j] > 0 && count[j] - aux[j] < 0) {
flag = false;
break;
}
}
if (flag) result.push(A[i]);
}
return result;
};
Input
words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
Output
["apple","google","leetcode"]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def wordSubsets(self, A: List[str], B: List[str]) -> List[str]:
cnt = collections.Counter()
for b in B:
for k, v in collections.Counter(b).items():
if cnt[k] < v:
cnt[k] = v
res = []
for a in A:
if not cnt - collections.Counter(a):
res.append(a)
return res
Input
words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
Output
["apple","google","leetcode"]