Number Of Valid Words For Each Puzzle - Leetcode Solution

Problem Statement: Given an array of strings words and a string puzzles, return an array answer, where answer[i] is the number of words in words that contains the ith puzzle letter and is a subset of the ith puzzle.

Note that each puzzle[i] can contain multiple letters, but each letter in the puzzle[i] is strictly unique.

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. Aboveyz contains 1 word that is a subset of "aaaa".
2. Abrodyz contains 1 word that is a subset of "aaaa".
3. Abslute contains 3 words that are a subset of "aaaa": "able", "ability", and "actt".
4. Absoryz contains 2 words that are a subset of "aaaa": "able" and "access".
5. Actresz contains 4 words that are a subset of "aaaa": "ability", "actt", "actor", and "access".
6. Gaswxyz has no words that are subsets of "aaaa".

Solution: We can see that the constraints for the puzzle are small, which indicates that we can use brute force to solve the problem. The basic idea is to iterate through each puzzle and for each puzzle, find all the words in the words array which contain the first letter of the puzzle. Then we check if these words are a subset of the puzzle. If yes, then we add 1 to the answer for this puzzle.

To optimize our solution, we can preprocess the words array to store a bitmap for each word. The bitmap will contain the frequency of each character in the word. For example, for the word "able", the bitmap will be [1,1,0,1,0,0,...,0]. Using this bitmap, we can easily find out if a word is a subset of the puzzle or not.

We can also preprocess the puzzles array by creating a set for each puzzle. This set will contain the unique characters of the puzzle. This will help us in filtering out words which do not contain any of the characters in the puzzle.

Here's the Python code implementation:

def findNumOfValidWords(words, puzzles):

# Preprocess words array
word_bitmaps = []
for word in words:
    bitmap = [0] * 26
    for char in word:
        bitmap[ord(char) - ord('a')] += 1
    word_bitmaps.append(bitmap)

# Preprocess puzzles array
puzzle_sets = []
for puzzle in puzzles:
    puzzle_sets.append(set(puzzle))

# Count valid words for each puzzle
answer = []
for puzzle_set in puzzle_sets:
    first_char = puzzle_set.pop()
    valid_words_count = 0
    for i, bitmap in enumerate(word_bitmaps):
        if first_char not in words[i]:
            continue
        if set(words[i]) - puzzle_set:
            continue
        if bitmap[ord(first_char) - ord('a')] == 0:
            continue
        valid_words_count += 1

    answer.append(valid_words_count)

return answer

Time complexity: The time complexity of the solution is O(n * m^2), where n is the length of the puzzles array and m is the average length of words in the words array. This is because we iterate through each puzzle and for each puzzle, we iterate through all the words and then check if the word is a subset of the puzzle. However, the actual time complexity will be much lower in practice because we are using several optimizations such as precomputing bitmaps and sets to filter out irrelevant words and puzzles.

1