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

class Solution {
public:
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){
for (int i = 0; i < 26; ++i){
if ((1 << i) & word_mask){
}
}
}
const int n = puzzles.size();
vector<int> ret(n, 0);
for (int i = 0; i < n; ++i){
auto p = puzzles[i];
for (auto & x: data[p - 'a']){
ret[i] += ((x & p_mask) == x);
}
}
return ret;
}
};

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

class Solution {
public:
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){
}
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 - 'a');
// find all subsets of this puzzle
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) + c)]
res.append(cur)
return res

Data Scientist/MLE/SWE @takemobi

More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi