from collections import Counter
from typing import *


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        record = Counter()
        for word in words:
            cur = 0
            for i in range(len(word)):
                cur |= 1 << (ord(word[i]) - ord('a'))
            record[cur] += 1

        rtn = []
        for puzzle in puzzles:
            first_bit = 1 << (ord(puzzle[0]) - ord('a'))
            bitmap = 0
            for i in range(1, len(puzzle)):
                bitmap |= 1 << (ord(puzzle[i]) - ord('a'))
            total = 0
            subset = bitmap
            while subset:
                s = subset | (1 << (ord(puzzle[0]) - ord("a")))
                if s in record:
                    total += record[s]
                subset = (subset - 1) & bitmap
            if first_bit in record:
                total += record[first_bit]

            rtn.append(total)
        return rtn


if __name__=='__main__':
    s = Solution()
    print(s.findNumOfValidWords(["aaaa","asas","able","ability","actt","actor","access"], ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]))
