With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

	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" (does not include 'a') and "based" (includes 's' which is not in the puzzle).
	
	

Return an array answer, where answer[i] is the number of words in the given word list words that is valid with respect to the puzzle puzzles[i].
&nbsp;
Example 1:

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 are no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.


Example 2:

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]


&nbsp;
Constraints:


	1 &lt;= words.length &lt;= 105
	4 &lt;= words[i].length &lt;= 50
	1 &lt;= puzzles.length &lt;= 104
	puzzles[i].length == 7
	words[i] and puzzles[i] consist of lowercase English letters.
	Each puzzles[i] does not contain repeated characters.


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        look_up=collections.defaultdict(int)
        def get_mask(word):
            mask=0
            for c in word:
                mask |= 1<<(ord(c)-ord('a'))
            return mask
        for word in words:
            mask=get_mask(word)
            look_up[mask]+=1
        ans=[]
        def solve(puzzle_idx,mask,c_idx):
            if c_idx==len(puzzles[puzzle_idx]):
                ans[-1]+=look_up[mask]
                return
            #take this c_idx
            solve(puzzle_idx,mask | 1<<(ord(puzzles[puzzle_idx][c_idx])-ord('a')),c_idx+1)
            #dont take this c_idx
            solve(puzzle_idx,mask,c_idx+1)
        for i,puzzle in enumerate(puzzles):
            ans.append(0)
            solve(i,1<<(ord(puzzle[0])-ord('a')),1)
        return ans
class Solution {

public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
    
    Map<Integer, Integer> map = new HashMap<>();
    
    for(String w : words){
        int mask = 0;
        for(int i = 0; i < w.length(); i++){
            mask |= 1 << (w.charAt(i) - 'a');
        }
        map.put(mask, map.getOrDefault(mask, 0) + 1);
    }
    
    List<Integer> res = new ArrayList<>();
    
    for(String p : puzzles){
        int mask = 0;
        for(int i = 0; i < p.length(); i++){
            mask |= 1 << (p.charAt(i) - 'a');
        }
        int c = 0;
        int sub = mask;
        int first = 1 << (p.charAt(0) - 'a');
        while(true){
            if((sub & first) == first && map.containsKey(sub)){
                c += map.get(sub);
            }
            
            if(sub == 0) break;
            
            sub = (sub - 1) & mask; // get the next substring
        }
        
        res.add(c);
    }
    
    return res;
}
}
class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        unordered_map<int, int> maskCnt;
        for(const auto& w: words) ++maskCnt[bitmask(w)];
        vector<int> ans(puzzles.size(), 0);
        for(int i = 0; i < puzzles.size(); i++){
            int mask, subMask = mask = bitmask(puzzles[i]), first = bitmask(puzzles[i].substr(0,1));
            do{
                if( (first & subMask) == first && maskCnt.count(subMask)) ans[i] += maskCnt[subMask]; //ok
            }while(subMask = (subMask - 1) & mask);
        }
        return ans;
    }

private:
    int bitmask(const string& word, int mask = 0){
        for(auto c: word) mask |= (1 << (c - 'a'));
        return mask;
    }
};
var findNumOfValidWords = function(words, puzzles) {
	// Form map of word's bitmasks
    const wordsMaskMap = words.reduce((map, word) => addToMap(map, getMask(word)), new Map())

    return puzzles.map(puzzle => {
        const pMask = getMask(puzzle)
        const pFirstMask = getFirstMask(puzzle)
        let count = 0
        
		// Verify each bitmask against a given puzzle
        for (let wMask of wordsMaskMap.keys()) {
            if((wMask & pFirstMask) && (!((wMask | pMask) ^ pMask))) {
                count += wordsMaskMap.get(wMask)
            }
        }
        return count
    })
}

// Transform a char into a bit index
var getBit = (char) => 1 << char.charCodeAt(0) - 'a'.charCodeAt(0)

// Transform a word into a bitmask
var getMask = (word) => word.split('').reduce((acc, c) => acc | getBit(c), 0)

// Get a bitmask for the first letter of a word
var getFirstMask = (word) => getBit(word[0])

// Helper function to count hashes in a Map object 
var addToMap = (map, val) => map.has(val) ? map.set(val, map.get(val) + 1) : map.set(val, 1)
Number of Valid Words for Each Puzzle