puzzle string, a word is valid if both the following conditions are satisfied:
word contains the first letter of puzzle.word, that letter is in puzzle.
"abcdefg", then valid words are "faced", "cabbage", and "baggage", while"beefed" (does not include 'a') and "based" (includes 's' which is not in the puzzle).answer, where answer[i] is the number of words in the given word list words that is valid with respect to the puzzle puzzles[i].
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] Explanation: 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]
Constraints:
1 <= words.length <= 1054 <= words[i].length <= 501 <= puzzles.length <= 104puzzles[i].length == 7words[i] and puzzles[i] consist of lowercase English letters.puzzles[i] does not contain repeated characters.Utilize bitmasks to represent words and puzzles. This allows for quick inclusion checks (using bitwise AND) and processing of the large dataset efficiently.
We construct a bitmask for each word and store it in a dictionary with counts. For each puzzle, generate all possible submasks (the example uses a different method) and check if they are present in the preprocessed dictionary.
The solution involves the following steps:
Time Complexity: O(W + P * 27), where W is the number of words and P is the number of puzzles.
Space Complexity: O(W), due to storing the bitmask of each word.
Loop through each puzzle and for each puzzle, check every word in the word list to see if it is valid. This approach is straightforward but inefficient for larger datasets.
Check each word against each puzzle, ensuring the word contains the first letter of the puzzle and no characters not in the puzzle. This approach is easy to understand but computationally expensive.
Time Complexity: O(W * P * L), where W is the number of words, P is the number of puzzles, and L is the average length of the words.
Space Complexity: O(1), as no additional data structures are used that scale with input size.
Using a bitmask, we can represent the presence of each letter in a word or puzzle as a single integer. Each bit in this integer corresponds to a letter from 'a' to 'z'.
For each word, compute its bitmask and store it in a hash map with its frequency. When processing puzzles, derive all potential subsets of the puzzle's bitmask that contain the first letter of the puzzle. Use the precomputed hash map to count how many words have matching character sets.
This solution first converts each word into a bitmask representing the presence of its characters using a get_bitmask function. The word_count dictionary stores the number of words for each bitmask.
For each puzzle, it generates the bitmask and processes each subset that includes the first puzzle letter using bit manipulation. It checks each subset against precomputed word masks for potential matches and counts them. This avoids unnecessary recomputation and efficiently selects valid words.
JavaScript
Time Complexity: O(N + P * 2^L), where N is the number of words, P is the number of puzzles, and L is the max number of letters in the puzzle (L = 7), resulting in 2^L subsets.
Space Complexity: O(N) for storing bitmasks and their frequencies.
This approach uses direct validation of each word against each puzzle by checking the conditions separately using set operations. Early stopping is applied if any character not in the puzzle is found or if the word doesn't contain the first puzzle character.
This Java solution leverages set membership tests for characters to ensure each word meets the puzzle's requirements. For each puzzle, it tracks characters in a set and verifies if each word abides by puzzle constraints, including early stopping.
The solution is less efficient for larger input sizes but straightforward to understand and implement directly.
Time Complexity: O(P * N * L), where P is the number of puzzles, N is the number of words, and L is the average length of each word.
Space Complexity: O(1) additional space besides input storage.
| Approach | Complexity |
|---|---|
| Bitmask Approach | Time Complexity: O(W + P * 27), where W is the number of words and P is the number of puzzles. |
| Brute Force Approach | Time Complexity: O(W * P * L), where W is the number of words, P is the number of puzzles, and L is the average length of the words. |
| Bitmasking with Precomputation | Time Complexity: O(N + P * 2^L), where N is the number of words, P is the number of puzzles, and L is the max number of letters in the puzzle (L = 7), resulting in 2^L subsets. Space Complexity: O(N) for storing bitmasks and their frequencies. |
| Direct Check with Early Stopping | Time Complexity: O(P * N * L), where P is the number of puzzles, N is the number of words, and L is the average length of each word. Space Complexity: O(1) additional space besides input storage. |
Valid Sudoku - Amazon Interview Question - Leetcode 36 - Python • NeetCode • 391,872 views views
Watch 9 more video solutions →Practice Number of Valid Words for Each Puzzle with our built-in code editor and test cases.
Practice on FleetCode