Number of Valid Words for Each Puzzle

Problem Description

Given a list of words and a list of puzzles, return an array where each element indicates the number of valid words for each corresponding puzzle. A word is valid if it contains the first letter of the puzzle and consists only of letters that are present in the puzzle.

Key Insights

• Each puzzle has a fixed length of 7 characters and does not contain repeated characters.
• A valid word must include the first letter of the puzzle.
• The letters in the word must all be found within the puzzle.
• A bitmask can be used to efficiently represent which letters are present in each word and puzzle.

Space and Time Complexity

Time Complexity: O(N * 2^7) where N is the number of words, as we consider each word and check its combination against the 7 letters of each puzzle. Space Complexity: O(N + M) where N is the number of words and M is the number of puzzles, for storing the bitmask representations.

Solution

To solve this problem, we utilize a bit manipulation approach. Each word and puzzle can be represented as a bitmask, where each bit corresponds to a letter in the alphabet. This allows for efficient checking of whether a word is valid for a given puzzle.

1. For each word, generate a bitmask that represents the characters in the word.
2. For each puzzle, also generate a bitmask.
3. Check if the first letter of the puzzle is present in the word's bitmask.
4. Verify that all letters in the word are included in the puzzle's bitmask using bitwise operations.
5. Count valid words for each puzzle and store the results.

Code Solutions