Description
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 = ["lc","eo"]
Output: ["leetcode"]
Example 3:
Input: words1 = ["acaac","cccbb","aacbb","caacc","bcbbb"], words2 = ["c","cc","b"]
Output: ["cccbb"]
Constraints:
1 <= words1.length, words2.length <= 1041 <= words1[i].length, words2[i].length <= 10words1[i] and words2[i] consist only of lowercase English letters.- All the strings of
words1 are unique.
Solutions
Solution 1: Counting
Traverse each word b in words2, count the maximum occurrence of each letter, and record it as cnt.
Then traverse each word a in words1, count the occurrence of each letter, and record it as t. If the occurrence of each letter in cnt is not greater than the occurrence in t, then a is a universal word, and add it to the answer.
The time complexity is O(L), where L is the sum of the lengths of all words in words1 and words2.
PythonJavaC++GoTypeScriptJavaScript
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(code-box)
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) {
ans.add(a);
}
}
return ans;
}
}(code-box)
class Solution {
public:
vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
int cnt[26] = {0};
int t[26];
for (auto& b : words2) {
memset(t, 0, sizeof t);
for (auto& c : b) {
t[c - 'a']++;
}
for (int i = 0; i < 26; ++i) {
cnt[i] = max(cnt[i], t[i]);
}
}
vector<string> ans;
for (auto& a : words1) {
memset(t, 0, sizeof t);
for (auto& c : a) {
t[c - 'a']++;
}
bool ok = true;
for (int i = 0; i < 26; ++i) {
if (cnt[i] > t[i]) {
ok = false;
break;
}
}
if (ok) {
ans.emplace_back(a);
}
}
return ans;
}
};(code-box)
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
}(code-box)
function wordSubsets(words1: string[], words2: string[]): string[] {
const cnt: number[] = Array(26).fill(0);
for (const b of words2) {
const t: number[] = Array(26).fill(0);
for (const c of b) {
t[c.charCodeAt(0) - 97]++;
}
for (let i = 0; i < 26; i++) {
cnt[i] = Math.max(cnt[i], t[i]);
}
}
const ans: string[] = [];
for (const a of words1) {
const t: number[] = Array(26).fill(0);
for (const c of a) {
t[c.charCodeAt(0) - 97]++;
}
let ok = true;
for (let i = 0; i < 26; i++) {
if (cnt[i] > t[i]) {
ok = false;
break;
}
}
if (ok) {
ans.push(a);
}
}
return ans;
}(code-box)
/**
* @param {string[]} words1
* @param {string[]} words2
* @return {string[]}
*/
var wordSubsets = function (words1, words2) {
const cnt = Array(26).fill(0);
for (const b of words2) {
const t = Array(26).fill(0);
for (const c of b) {
t[c.charCodeAt(0) - 97]++;
}
for (let i = 0; i < 26; i++) {
cnt[i] = Math.max(cnt[i], t[i]);
}
}
const ans = [];
for (const a of words1) {
const t = Array(26).fill(0);
for (const c of a) {
t[c.charCodeAt(0) - 97]++;
}
let ok = true;
for (let i = 0; i < 26; i++) {
if (cnt[i] > t[i]) {
ok = false;
break;
}
}
if (ok) {
ans.push(a);
}
}
return ans;
};(code-box)
