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;
    }
};