# Solution 1: brute force by organizing the words in 26 categories (run time 1016 ms).

`class Solution {    public:    int get_word_mask(string &word){        int ret = 0;        for (auto & ch: word){            ret |= (1 << (ch - 'a'));        }        return ret;    }    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {        vector<vector<int>> data(26);        for (auto &word: words){            auto word_mask = get_word_mask(word);            for (int i = 0; i < 26; ++i){                if ((1 << i) & word_mask){                    if(__builtin_popcount(word_mask) <= 7) data[i].push_back(word_mask);                }            }        }        const int n = puzzles.size();        vector<int> ret(n, 0);        for (int i = 0; i < n; ++i){            auto p = puzzles[i];            auto p_mask = get_word_mask(p);            for (auto & x: data[p[0] - 'a']){                ret[i] += ((x & p_mask) == x);            }        }        return ret;}};`

# Solution 2: Check each subset of a puzzle (108 ms).

`class Solution {    public:    int get_word_mask(string &word){        int ret = 0;        for (auto & ch: word){            ret |= (1 << (ch - 'a'));        }        return ret;    }    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {        unordered_map<int, int> m;        for (auto &word: words){            auto word_mask = get_word_mask(word);            if (__builtin_popcount(word_mask) > 7) continue;            m[word_mask]++;}        const int n = puzzles.size();        vector<int> ret(n, 0);        for (int i = 0; i < n; ++i){            auto p = puzzles[i];            int p_subset = 1 << (p[0] - 'a');            // find all subsets of this puzzle            for (int mask = 0; mask < (1 << 6); ++mask){                int this_subset = p_subset;                for (int k = 0; k < 6; ++k){                    if ((1 << k) & mask){                        this_subset |= 1 << (p[k+1]-'a');                    }                }                ret[i] += m[this_subset];            }}        return ret;}};`
`class Solution:    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:        count = collections.Counter(frozenset(w) for w in words)        res = []        for p in puzzles:            cur = 0            for k in range(len(p)):                for c in itertools.combinations(p[1:], k):                    cur += count[frozenset(tuple(p[0]) + c)]            res.append(cur)        return res`

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi