# Number of Valid Words for Each Puzzle

With respect to a given puzzlewordvalid

• word contains the first letter of puzzle.
• For each letter in word, that letter is in puzzle. For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”; while invalid words are “beefed” (doesn’t include “a”) and “based” (includes “s” which isn’t in the puzzle).

Return an array answeranswer[i]wordspuzzles[i]

Example :

Input:
words = ["aaaa","asas","able","ability","actt","actor","access"],
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation:
1 valid word for "aboveyz" : "aaaa"
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There're no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.


Constraints:

• 1 <= words.length <= 10^5
• 4 <= words[i].length <= 50
• 1 <= puzzles.length <= 10^4
• puzzles[i].length == 7
• words[i][j], puzzles[i][j] are English lowercase letters.
• Each puzzles[i] doesn’t contain repeated characters.

Solution:

Use bitmap to store each string in word. 1 for presense of letter c-‘a’. Use map to store count for each word bitmap.

Because puzzle length = 7, and the first one must be present, so there are 2^6 = 64 possiblities for each puzzle. Generate the possibilities and add up the counts.

class Solution {
public:
vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
unordered_map<int,int> ws;
for(int i = 0;i < words.size(); i++){
string w = words[i];
int temp = 0;
int cnt = 0;
for(char c: w){
if(temp & (1<<(c-'a'))) continue;
cnt++;
if(cnt > 7) break;
temp |= (1 << (c-'a'));
}
if(cnt>7) continue;
ws[temp]++;
}

vector<int> ans(puzzles.size(), 0);
for(int i=0;i<puzzles.size();i++){
string p = puzzles[i];

for(int j = 0; j< (1<<6); j++){
int ptemp = (1 << (p[0] - 'a'));
for(int k = 0; k < 6;k++){
if(j & (1<<k)){
ptemp |= (1<< (p[k+1] - 'a'));
}
}

ans[i] += ws[ptemp];
}
}
return ans;
}
};