Word Subsets

Leetcode Problem:

• Word Subsets

Summary

• Given two string arrays, find all the universal strings in the first array that can form a subset of every string in the second array.

Approach

• The approach used is to first count the frequency of each character in all strings of the second array
• Then, for each string in the first array, check if it can form a subset of every string in the second array by comparing the frequency of each character in the string with the minimum count from the second array
• If a string can form a subset of every string in the second array, it is added to the result.

Complexity

• O(n * m * 26) where n is the number of strings in the first array, m is the number of strings in the second array, and 26 is the number of lowercase English letters.

Explanation

• The solution uses a character count array `charCnt` to store the minimum frequency of each character in the second array
• It then iterates over each string in the first array and checks if it can form a subset of every string in the second array by comparing the frequency of each character in the string with the minimum count from the second array
• If a string can form a subset of every string in the second array, it is added to the result.

Solution Code:

class Solution {
public:
    int charCnt[128];
    vector wordSubsets(vector& words1, vector& words2) {
        for(string word : words2){
            int tmpCnt[128] = {0};
            for(char c : word){
                tmpCnt[c]++;
            }
            for(int i = 'a' ; i <= 'z'; i++){
                charCnt[i] = max(charCnt[i], tmpCnt[i]);
            }
        }
        vector ans;
        for(string word : words1){
            int tmpCnt[128] = {0};
            for(char c : word){
                tmpCnt[c]++;
            }
            bool isSubset = true;
            for(int i = 'a' ; i <= 'z'; i++){
                if(charCnt[i] == 0) continue;
                if(tmpCnt[i] < charCnt[i]){
                    isSubset = false;
                    break;
                }
            }
            if(isSubset){
                ans.push_back(word);
            }
        }
        return ans;
    }
};