Number of Valid Words for Each Puzzle — Bitmask Subset

Problem

A word is valid for a puzzle if: (1) word contains puzzle[0], (2) all letters of word are in puzzle. Count valid words per puzzle.

Approach — Bitmask + Subset Enumeration

Encode each word as a bitmask of letters. For each puzzle, enumerate all subsets of its 7 letters that include puzzle[0]; look up count in hashmap.

Time: O(n * L + q * 2^7) | Space: O(n)

Solutions

Python

from collections import defaultdict
class Solution:
    def findNumOfValidWords(self, words: list[str], puzzles: list[str]) -> list[int]:
        word_counts=defaultdict(int)
        for w in words:
            mask=0
            for c in w: mask|=(1<<(ord(c)-ord('a')))
            if bin(mask).count('1')<=7: word_counts[mask]+=1
        res=[]
        for p in puzzles:
            pmask=0
            for c in p: pmask|=(1<<(ord(c)-ord('a')))
            first=1<<(ord(p[0])-ord('a'))
            count=0; sub=pmask
            while sub:
                if sub&first: count+=word_counts[sub]
                sub=(sub-1)&pmask
            res.append(count)
        return res

Complexity

Time: O(nL + q2^7) | Space: O(n)