916. Word Subsets

起初用了所有A對所有Ｂ的比對, 花了O(N²)太久了

後來發現我只要B字串中每個字母出現的最大值即可, 所以比對只要比一組array就好了 時間複雜度為O(n)

class Solution {
public:
    vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
        vector<string> res;
        vector<int> b_set(26, 0);
        for(auto b: B) {
            vector<int> letter(26, 0);
            for(auto c: b){
                letter[c - 'a']++;
            }
            for(int i = 0; i < 26;i++){
                b_set[i] = max(letter[i], b_set[i]);
            }
        }
        for(auto a: A){
            vector<int> letter(26, 0);
            for(auto c: a){
                letter[c - 'a']++;
            }
            bool flag = true;
            for(int k = 0;k < 26; k++){
              if(letter[k] < b_set[k]){
                  flag = false;
                  break;
              }
            }
            if(flag){
                res.push_back(a);
            }
        }
       
        return res;
    }
};