Formatted question description: https://leetcode.ca/all/916.html

916. Word Subsets (Medium)

We are given two arrays A and B of words.  Each word is a string of lowercase letters.

Now, say that word b is a subset of word 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".

Now say a word a from A is universal if for every b in B, b is a subset of a

Return a list of all universal words in A.  You can return the words in any order.

Example 1:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]


Example 2:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]


Example 3:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]


Example 4:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]


Example 5:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]


Note:

1. 1 <= A.length, B.length <= 10000
2. 1 <= A[i].length, B[i].length <= 10
3. A[i] and B[i] consist only of lowercase letters.
4. All words in A[i] are unique: there isn't i != j with A[i] == A[j].

Related Topics:
String

Solution 1.

• class Solution {
public List<String> wordSubsets(String[] A, String[] B) {
List<String> universalList = new ArrayList<String>();
int[] counts = getMaxCounts(B);
for (String word : A) {
int[] wordCounts = getWordCounts(word);
boolean flag = true;
for (int i = 0; i < 26; i++) {
if (wordCounts[i] < counts[i]) {
flag = false;
break;
}
}
if (flag)
}
return universalList;
}

public int[] getMaxCounts(String[] array) {
int[] counts = new int[26];
for (String word : array) {
int[] curCounts = new int[26];
char[] wordArray = word.toCharArray();
for (char c : wordArray)
curCounts[c - 'a']++;
for (int i = 0; i < 26; i++)
counts[i] = Math.max(counts[i], curCounts[i]);
}
return counts;
}

public int[] getWordCounts(String word) {
int[] wordCounts = new int[26];
char[] wordArray = word.toCharArray();
for (char c : wordArray)
wordCounts[c - 'a']++;
return wordCounts;
}
}

############

class Solution {
public List<String> wordSubsets(String[] words1, String[] words2) {
int[] cnt = new int[26];
for (var b : words2) {
int[] t = new int[26];
for (int i = 0; i < b.length(); ++i) {
t[b.charAt(i) - 'a']++;
}
for (int i = 0; i < 26; ++i) {
cnt[i] = Math.max(cnt[i], t[i]);
}
}
List<String> ans = new ArrayList<>();
for (var a : words1) {
int[] t = new int[26];
for (int i = 0; i < a.length(); ++i) {
t[a.charAt(i) - 'a']++;
}
boolean ok = true;
for (int i = 0; i < 26; ++i) {
if (cnt[i] > t[i]) {
ok = false;
break;
}
}
if (ok) {
}
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/word-subsets/
// Time: O((A + B) * N) where N is the maximum length of string
// Space: O(1)
class Solution {
public:
vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
int N = A.size(), target[26] = {}, j = 0;
for (auto &b : B) {
int cnt[26] = {};
for (char c : b) cnt[c - 'a']++;
for (int i = 0; i < 26; ++i) target[i] = max(target[i], cnt[i]);
}
for (int i = 0; i < N; ++i) {
int cnt[26] = {};
for (char c : A[i]) cnt[c - 'a']++;
bool valid = true;
for (int k = 0; k < 26 && valid; ++k) valid = target[k] <= cnt[k];
if (valid) A[j++] = A[i];
}
A.resize(j);
return A;
}
};

• class Solution:
def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
cnt = Counter()
for b in words2:
t = Counter(b)
for c, v in t.items():
cnt[c] = max(cnt[c], v)
ans = []
for a in words1:
t = Counter(a)
if all(v <= t[c] for c, v in cnt.items()):
ans.append(a)
return ans

############

class Solution(object):
def wordSubsets(self, A, B):
"""
:type A: List[str]
:type B: List[str]
:rtype: List[str]
"""
B = set(B)
res = []
count = collections.defaultdict(int)
for b in B:
cb = collections.Counter(b)
for c, v in cb.items():
count[c] = max(count[c], v)
res = []
for a in A:
ca = collections.Counter(a)
isSuccess = True
for c, v in count.items():
if v > ca[c]:
isSuccess = False
break
if isSuccess:
res.append(a)
return res

• func wordSubsets(words1 []string, words2 []string) (ans []string) {
cnt := [26]int{}
for _, b := range words2 {
t := [26]int{}
for _, c := range b {
t[c-'a']++
}
for i := range cnt {
cnt[i] = max(cnt[i], t[i])
}
}
for _, a := range words1 {
t := [26]int{}
for _, c := range a {
t[c-'a']++
}
ok := true
for i, v := range cnt {
if v > t[i] {
ok = false
break
}
}
if ok {
ans = append(ans, a)
}
}
return
}

func max(a, b int) int {
if a > b {
return a
}
return b
}