916: Word-Subsets
Medium

table of contents

This question speaks to me like a Hash Map question.

My algorithm simply checks each word in words2 and generates an alphabet array counting the maximum number of each letter (of the alphabet) present in any word of words2. Then, you simply iterate through words1 and check for universal strings, by checking all the letter counts in words1[i] is greater than or equal to the letter counts in alphabet.

code

class Solution {
public:
    vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        int alphabet[26] = {0};
        int counter = 0;
        for (string word : words2) {
            int temp_alphabet[26] = {0};
            for (char c : word) {
                ++temp_alphabet[c-'a'];
            }
            for (int i = 0; i < 26; ++i) {
                alphabet[i] = max(alphabet[i], temp_alphabet[i]);
            }
        }
        vector<string> ans;
        bool isUniversal;
        for (string word : words1) {
            int temp_alphabet[26] = {0};
            for (char c : word) {
                ++temp_alphabet[c-'a'];
            }
            isUniversal = true;
            for (int i = 0; i < 26; ++i) {
                if (temp_alphabet[i] < alphabet[i]) {
                    isUniversal = false;
                    break;
                }
            }
            if (isUniversal == true) {
                ans.push_back(word);
            }
        }
        return ans;
    }
};

complexity