916. Word Subsets -------M ~~~~~看一步步的精简过程

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

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;
    }
};