from collections import Counter
from typing import List
class Solution:
def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
max_count = Counter()
for b in words2:
b_count = Counter(b)
for char in b_count:
max_count[char] = max(max_count[char], b_count[char])
res = []
for a in words1:
a_count = Counter(a)
if all(a_count[char] >= max_count[char] for char in max_count):
res.append(a)
return res
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
vector<int> maxCount(26, 0);
for (const string& b : words2) {
vector<int> bCount(26, 0);
for (char c : b)
bCount[c - 'a']++;
for (int i = 0; i < 26; ++i)
maxCount[i] = max(maxCount[i], bCount[i]);
}
vector<string> res;
for (const string& a : words1) {
vector<int> aCount(26, 0);
for (char c : a)
aCount[c - 'a']++;
bool valid = true;
for (int i = 0; i < 26; ++i) {
if (aCount[i] < maxCount[i]) {
valid = false;
break;
}
}
if (valid)
res.push_back(a);
}
return res;
}
};
import java.util.*;
class Solution {
public List<String> wordSubsets(String[] words1, String[] words2) {
int[] maxCount = new int[26];
for (String b : words2) {
int[] bCount = new int[26];
for (char c : b.toCharArray()) {
bCount[c - 'a']++;
}
for (int i = 0; i < 26; ++i) {
maxCount[i] = Math.max(maxCount[i], bCount[i]);
}
}
List<String> res = new ArrayList<>();
for (String a : words1) {
int[] aCount = new int[26];
for (char c : a.toCharArray()) {
aCount[c - 'a']++;
}
boolean valid = true;
for (int i = 0; i < 26; ++i) {
if (aCount[i] < maxCount[i]) {
valid = false;
break;
}
}
if (valid) res.add(a);
}
return res;
}
}
/**
* @param {string[]} words1
* @param {string[]} words2
* @return {string[]}
*/
var wordSubsets = function(words1, words2) {
let maxCount = new Array(26).fill(0);
for (let b of words2) {
let bCount = new Array(26).fill(0);
for (let c of b) {
bCount[c.charCodeAt(0) - 97]++;
}
for (let i = 0; i < 26; ++i) {
maxCount[i] = Math.max(maxCount[i], bCount[i]);
}
}
let res = [];
for (let a of words1) {
let aCount = new Array(26).fill(0);
for (let c of a) {
aCount[c.charCodeAt(0) - 97]++;
}
let valid = true;
for (let i = 0; i < 26; ++i) {
if (aCount[i] < maxCount[i]) {
valid = false;
break;
}
}
if (valid) res.push(a);
}
return res;
};
You are given two string arrays: words1 and words2. A string a from words1 is considered a universal word if for every string b in words2, a contains all the letters in b (including duplicates). In other words, for each character in b, a must have at least as many occurrences of that character as b does.
Your task is to return all universal words from words1 as an array.
words2, and a universal word must satisfy the requirement for all of them.words1 can be used at most once in the answer.
At first glance, it may seem necessary to check each word in words1 against every word in words2, verifying for each if all required letters are present in sufficient quantity. This brute-force approach, however, may become inefficient as the input size grows.
The key insight is that the requirements from words2 can be combined: for each letter, what is the maximum number of times it is needed in any words2 word? If a word from words1 meets these maximum requirements for every letter, it will be universal for all words2.
By transforming words2 into a single "maximum letter frequency" requirement, we can check each words1 word just once against this combined profile, greatly reducing the number of checks.
We will follow these steps to solve the problem efficiently:
words2, count the frequency of each letter.
words2 words.
words1:
words1, count its letter frequencies.
We use hash maps (or arrays for 26 letters) for fast frequency counting and comparison.
Input:
words1 = ["amazon", "apple", "facebook", "google", "leetcode"]
words2 = ["e", "o"]
words2:
words1:
words1 (length N), check against each word in words2 (length M), and for each letter (up to 26). Time: O(N * M * L), where L is the average word length.
words1, counting letters and comparing: O(N * L)
The Word Subsets problem can be efficiently solved by reducing the requirements from words2 into a single "maximum letter frequency" profile, and then checking each word in words1 against this profile. This avoids redundant checking and leverages fast frequency counting, resulting in a clear, elegant, and efficient solution.