# 916. Word Subsets

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"]
Output: ["facebook","google","leetcode"]
``````

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

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

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]`.

``````class Solution {
public:
vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
vector<string> res;
vector<int> charCnt(26);
for (string &b : B) {
vector<int> t = helper(b);
for (int i = 0; i < 26; ++i) {
charCnt[i] = max(charCnt[i], t[i]);
}
}
for (string &a : A) {
vector<int> t = helper(a);
int i = 0;
for (; i < 26; ++i) {
if (t[i] < charCnt[i]) break;
}
if (i == 26) res.push_back(a);
}
return res;
}
vector<int> helper(string& word) {
vector<int> res(26);
for (char c : word) ++res[c - 'a'];
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/916

https://leetcode.com/problems/word-subsets/

https://leetcode.com/problems/word-subsets/discuss/175854/C%2B%2BJavaPython-Straight-Forward

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation