Word Subsets

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

• Time: O(n+m) (if n & m represents the total information in words1 and words2 respectively)
• Space: O(n)