#1178

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Valid Words for Each Puzzle

Solve the "Number of Valid Words for Each Puzzle" problem with array scanning and hash lookup to efficiently count valid words for each puzzle.

array hash table string bit manipulation trie

Problem Statement

You are given an array of words and an array of puzzles. Each word is formed by lowercase English letters, and each puzzle is a string of exactly 7 unique lowercase letters.

For each puzzle, you need to count how many words from the words array can be formed by characters present in the puzzle string, ensuring that the puzzle's first letter is always included in the word. The challenge is to do this efficiently, considering the large input size.

Examples

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]

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]

Example details omitted.

Constraints

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

Solution Approach

Bit Masking

A bitmask can represent each word and puzzle efficiently. Convert both the words and the puzzles into bitmask representations, where each bit corresponds to a specific character in the alphabet. This allows us to quickly compare if a word's characters are a subset of the puzzle's characters.

Precompute Word Masks

Precompute the bitmask for each word in the words array. Use a hash table to store the frequency of each bitmask, so that for each puzzle, you can check how many of the words' bitmasks match the puzzle's bitmask.

Optimize by Puzzle Constraints

The fact that puzzles are only 7 characters long is key to optimizing the solution. For each puzzle, you only need to check the words whose masks are subsets of the puzzle’s bitmask, which greatly reduces the number of comparisons.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on how efficiently the bitmask comparisons are handled. Precomputing the bitmasks for all words takes O(n) time, where n is the number of words. For each puzzle, checking valid words using bitmask operations takes O(1) per word, leading to an overall time complexity of O(n + m), where m is the number of puzzles. Space complexity is also O(n) due to storing word bitmasks in a hash table.

What Interviewers Usually Probe

Understanding bitmasking and its application to problems with constraints on character sets.
Efficient handling of large datasets, particularly when there are multiple queries for the same input.
Effective use of hash tables and bit manipulation to avoid brute-force solutions.

Common Pitfalls or Variants

Common pitfalls

Not accounting for the first letter of each puzzle word, which is required to be part of every valid word.
Using brute force to check every word against every puzzle, leading to inefficient solutions.
Overlooking the need to optimize for the fact that puzzles are only 7 characters long, missing the opportunity for bitmask comparisons.

Follow-up variants

Consider handling cases with more complicated character sets or larger puzzle sizes.
Explore how the problem might change if the number of words or puzzles grows beyond the current constraints.
Test variations where words or puzzles contain repeated characters or longer lengths, which will impact the approach.

FAQ

What is the best approach to solve the "Number of Valid Words for Each Puzzle" problem?

The best approach is using bitmasking to efficiently represent both words and puzzles, combined with hash tables to count the valid word matches for each puzzle.

How can I optimize my solution for "Number of Valid Words for Each Puzzle"?

Optimize by precomputing bitmasks for all words, storing them in a hash table, and using bitwise operations to check for valid word matches for each puzzle.

What role does the 7-character length of the puzzles play in this problem?

The 7-character length is crucial for optimization, as it limits the number of possible characters in each puzzle, making bitmasking an efficient solution for comparing words.

What is the time complexity of the "Number of Valid Words for Each Puzzle" problem?

The time complexity is O(n + m), where n is the number of words and m is the number of puzzles, due to precomputing word bitmasks and efficiently checking valid words for each puzzle.

Can I use a brute-force approach for this problem?

While a brute-force approach is possible, it is inefficient. The optimal solution leverages bitmasking and hash tables to significantly reduce computational complexity.

terminal

Solution

Solution 1: State Compression + Hash Table + Subset Enumeration

According to the problem description, for each puzzle $p$ in the puzzle array $puzzles$, we need to count how many words $w$ contain the first letter of the puzzle $p$, and every letter in $w$ can be found in $p$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        cnt = Counter()
        for w in words:
            mask = 0
            for c in w:
                mask |= 1 << (ord(c) - ord("a"))
            cnt[mask] += 1

        ans = []
        for p in puzzles:
            mask = 0
            for c in p:
                mask |= 1 << (ord(c) - ord("a"))
            x, i, j = 0, ord(p[0]) - ord("a"), mask
            while j:
                if j >> i & 1:
                    x += cnt[j]
                j = (j - 1) & mask
            ans.append(x)
        return ans

Continue Practicing

#1177 can make palindrome from substring #820 short encoding of words #792 number of matching subsequences