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 <= A.length, B.length <= 10000
1 <= A[i].length, B[i].length <= 10
A[i]
andB[i]
consist only of lowercase letters.- All words in
A[i]
are unique: there isn'ti != j
withA[i] == A[j]
.
A:
首先,我们搞成vector count , 然后一个个对比。 结果不出意外,LTE了
class Solution { public: vector<string> wordSubsets(vector<string>& A, vector<string>& B) { unordered_map<string, vector<int>> MA; for(auto a : A){ vector<int> tmp(26,0); for(auto ch : a){ tmp[ch-'a']++; } MA[a] = tmp; } unordered_map<string, vector<int>> MB; for(auto b : B){ vector<int> tmp(26,0); for(auto ch : b){ tmp[ch-'a']++; } MB[b] = tmp; } vector<string> res; for(auto &a : A){ auto& va = MA[a]; bool matched = true; for(auto it : MB){ auto vb = it.second; for(int i =0;i<26;i++){ if(va[i]<vb[i]){ matched = false; break; } } if(not matched){ break; } } if(matched){ res.push_back(a); } } return res; } };
研究发现, B 中会有重复的, 还有就是有些是包含关系(然而包含关系,不能简单取消)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | class Solution { public: vector<string> wordSubsets(vector<string>& A, vector<string>& B) { unordered_map<string, vector<int>> MA; for(auto a : A){ vector<int> tmp(26,0); for(auto ch : a){ tmp[ch-'a']++; } MA[a] = tmp; } unordered_set<string> SB; for(auto b : B){ sort(b.begin(), b.end()); SB.insert(b); } vector<vector<int>> VB; for(auto it : SB){ vector<int> tmp(26,0); for(auto ch : it){ tmp[ch-'a']++; } VB.push_back(tmp); } vector<string> res; for(auto &a : A){ auto& va = MA[a]; bool matched = true; for(auto vb : VB){ matched = allBigger(va, vb); if(not matched){ break; } } if(matched){ res.push_back(a); } } return res; } private: bool allBigger(vector<int>& va, vector<int>& vb){ for(int i =0;i<26;i++){ if(va[i]<vb[i]){ return false; } } return true; } }; |
然而,对于某些结果, 还是LTE了。
继续精简B。 找到每个字母的最大值。
也就是,对于每一个letter,我们只记录其最大的出现的过程。 满足那个即可。
class Solution { public: vector<string> wordSubsets(vector<string>& A, vector<string>& B) { vector<int> vb(26,0); for(auto it : B){ vector<int> tmp(26,0); for(auto ch : it){ tmp[ch-'a']++; } for(int i =0;i<26;i++){ vb[i] = max(vb[i], tmp[i]); } } vector<string> res; for(auto &a : A){ vector<int> tmp(26,0); for(auto ch : a){ tmp[ch-'a']++; } if(allBigger(tmp, vb)){ res.push_back(a); } } return res; } private: bool allBigger(vector<int>& va, vector<int>& vb){ for(int i =0;i<26;i++){ if(va[i]<vb[i]){ return false; } } return true; } };
No comments:
Post a Comment