Saturday, October 17, 2020

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



    No comments:

    Post a Comment