Problem Statement
In the given task, we are asked to evaluate a list of words against specific puzzle conditions defined by a list of puzzle strings. Each puzzle stipulates two criteria for a word to be considered valid:
- The word must contain the first letter of the given puzzle.
- All letters in the word must be present in the puzzle string.
The goal is to compute the number of valid words per each puzzle string provided and return these counts in an array. Each index in the output should correspond to the respective puzzle in the input list.
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]
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]andpuzzles[i]consist of lowercase English letters.- Each
puzzles[i]does not contain repeated characters.
Approach and Intuition
To approach this problem efficiently, we can utilize the following insights based on the examples and constraints provided:
- Focus on the first letter of each puzzle, as any word that doesn't contain this letter can be immediately disregarded for that particular puzzle.
- Use a hash set for each puzzle and word:
- Convert each puzzle and word into a set of characters for quick look-up and comparison.
- This helps to check if a word can be formed using the characters in the puzzle.
- Iterate through each puzzle:
- For each puzzle, check each word to determine if it's valid by:
- Ensuring the first character of the puzzle appears in the word.
- Verifying that all characters in the word are in the current puzzle set.
- Increment the count of valid words for that particular puzzle.
- For each puzzle, check each word to determine if it's valid by:
Given the constraints, where the length of the puzzles is always 7, and words can be quite long, using set operations (intersection, subset checking) on puzzles and words offers a balance between computational efficiency and implementation complexity. The conversion of puzzles and words into set form helps speed up the process of checking whether a word's characters are all present in a puzzle, and whether the word contains the puzzle's first letter.
In summary, our solution revolves around transforming the puzzles and words into a more easily comparable form (like sets), and then leveraging the properties of sets to quickly assess the validity criteria dictated by the puzzles.
Solutions
- C++
- Java
- Python
class Solution {
public:
vector<int> countValidWords(vector<string>& words, vector<string>& puzzles) {
int MAX_CHARS = 26; // Define number of characters in the alphabet
vector<vector<int>> wordTrie = {vector<int>(MAX_CHARS)}; // Trie implementation with a vector
vector<int> endpointCount = {0}; // Count of words ending at each node in the trie
for (string word : words) { // Process each word
sort(word.begin(), word.end()); // Sort and remove duplicates
word.erase(unique(word.begin(), word.end()), word.end());
if (word.length() <= 7) { // If more than 7 unique letters, cannot be puzzle first letter
int trieNode = 0;
for (char ch : word) { // Insert word into trie
int idx = ch - 'a';
if (wordTrie[trieNode][idx] == 0) {
wordTrie.push_back(vector<int>(MAX_CHARS));
endpointCount.push_back(0);
wordTrie[trieNode][idx] = wordTrie.size() - 1;
}
trieNode = wordTrie[trieNode][idx];
}
endpointCount[trieNode]++;
}
}
// DFS to find valid words that match puzzles
function<int(int, bool, string&)> traverseTrie = [&](int node, bool containsFirst, string& puzzle) {
int matchedWords = containsFirst ? endpointCount[node] : 0;
for (char ch : puzzle) {
int idx = ch - 'a';
if (wordTrie[node][idx]) {
matchedWords += traverseTrie(wordTrie[node][idx], containsFirst || (ch == puzzle[0]), puzzle);
}
}
return matchedWords;
};
vector<int> results;
for (string& puzzle : puzzles) { // For each puzzle, calculate the number of valid words
results.push_back(traverseTrie(0, false, puzzle));
}
return results;
}
};
The provided C++ solution aims to determine the number of valid words for each puzzle using Trie and Depth-First Search (DFS) strategies. The process involves steps where a trie is built from the given words after sorting and deduplicating them, ensuring that each word doesn't contain more than seven unique characters to be considered a potential puzzle. For each puzzle, a DFS algorithm traverses the trie to calculate the number of words matching the puzzle's criteria. Here's a step-by-step breakdown of the algorithm:
- Initialize the trie and a vector to count the number of words ending at each trie node.
- For each word, verify it has 7 or fewer unique letters. Sort the word, remove duplicates, and insert it into the trie.
- Use a DFS function to check if each puzzle contains words from the words list. It traverses the trie and adds up the valid words that satisfy the puzzle's of having the first letter and being a subset of its letters.
- Return a vector representing the count of valid words for each puzzle.
The algorithm efficiently organizes and searches through possible word combinations with the trie structure, ensuring a quick and accurate determination of each puzzle's valid words. Additionally, by pre-processing words to ensure uniqueness and length constraints, the solution optimizes performance by avoiding unnecessary computations during the DFS traversal.
class Solution {
public List<Integer> countValidWords(String[] words, String[] puzzles) {
int ALPHABET_SIZE = 26; // size of the alphabet
ArrayList<Integer[]> wordTree = new ArrayList<>(); // simulate trie with list
wordTree.add(Collections.nCopies(ALPHABET_SIZE, 0).toArray(new Integer[0]));
ArrayList<Integer> wordEndCount = new ArrayList<>(List.of(0)); // counts of words ending at a node index
for (String word : words) {
// process to remove duplicate letters and sort
char[] characters = word.toCharArray();
Arrays.sort(characters);
StringBuilder uniqueChars = new StringBuilder();
uniqueChars.append(characters[0]);
for (int i = 1; i < characters.length; i++) {
if (characters[i] != characters[i - 1]) {
uniqueChars.append(characters[i]);
}
}
if (uniqueChars.length() <= 7) { // skip words longer than 7 characters
// insert the word into the trie
int nodeIndex = 0;
for (char letter : uniqueChars.toString().toCharArray()) {
int index = letter - 'a';
if (wordTree.get(nodeIndex)[index] == 0) { // add a new node if absent
wordTree.add(Collections.nCopies(ALPHABET_SIZE, 0).toArray(new Integer[0]));
wordEndCount.add(0);
wordTree.get(nodeIndex)[index] = wordTree.size() - 1;
}
nodeIndex = wordTree.get(nodeIndex)[index];
}
wordEndCount.set(nodeIndex, wordEndCount.get(nodeIndex) + 1);
}
}
ArrayList<Integer> solution = new ArrayList<>();
for (String puzzle : puzzles) {
solution.add(search(0, false, puzzle, wordTree, wordEndCount));
}
return solution;
}
// Helper method to perform dfs search in the trie
int search(int currentNode, boolean firstLetterIn, String puzzle, List<Integer[]> wordTree, List<Integer> wordCount) {
int validWordsCount = firstLetterIn ? wordCount.get(currentNode) : 0;
for (char ch : puzzle.toCharArray()) {
int idx = ch - 'a';
if (wordTree.get(currentNode)[idx] > 0) {
validWordsCount += search(wordTree.get(currentNode)[idx], firstLetterIn || (ch == puzzle.charAt(0)), puzzle, wordTree, wordCount);
}
}
return validWordsCount;
}
}
The provided Java solution for the "Number of Valid Words for Each Puzzle" problem counts how many words from a given list are valid for each puzzle. The core idea is to preprocess the words into a data structure to efficiently check against each puzzle's constraints.
The solution uses a trie-like data structure (wordTree) and a list (wordEndCount) to store counts of words ending at each node of the trie. This approach supports quick lookups during puzzle processing:
- Start by defining constants and initializing structures,
wordTreeto simulate the trie, andwordEndCountto count words. - For each word, remove duplicates and ensure they are in sorted order, ignoring those longer than 7 characters as per given constraints.
- Insert each processed word into the trie (
wordTree), updating the count of word endings inwordEndCountappropriately. - For each puzzle, call the
searchmethod, passing in the trie, word counts, and puzzle details to compute the number of valid words. - Within the
searchmethod, perform a depth-first search (DFS) in the trie. The search considers whether the first letter of the puzzle has been included in the current path. It recursively counts and sums up the valid words for sub-paths of the trie.
The search method is crucial for counting valid words for a given puzzle, leveraging the trie to deeply explore possible word paths effectively and verifying them against puzzle constraints.
Overall, this method offers an optimized approach to the problem by reducing the operation from potentially exponential to polynomial time, depending on the initial word and puzzle sizes via efficient data structuring and processing.
class WordPuzzleSolver:
def numberOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
# Initialize constants and trie structure
ALPHABET_LENGTH = 26
trie_root = [[0] * ALPHABET_LENGTH]
word_terminal_count = [0]
# Build trie for unique, sorted words with length <= 7
for word in words:
processed_word = sorted(set(word))
if len(processed_word) <= 7:
node_index = 0
for character in processed_word:
char_index = ord(character) - ord('a')
if not trie_root[node_index][char_index]:
trie_root.append([0] * ALPHABET_LENGTH)
word_terminal_count.append(0)
trie_root[node_index][char_index] = len(trie_root) - 1
node_index = trie_root[node_index][char_index]
word_terminal_count[node_index] += 1
# Define a DFS function for calculating valid words per puzzle
def searchTrie(trie_id, first_letter_matched):
valid_words_count = word_terminal_count[trie_id] if first_letter_matched else 0
for character in current_puzzle:
char_index = ord(character) - ord('a')
if trie_root[trie_id][char_index]:
valid_words_count += searchTrie(trie_root[trie_id][char_index], first_letter_matched or character == current_puzzle[0])
return valid_words_count
# Process each puzzle and store results
results = []
for current_puzzle in puzzles:
results.append(searchTrie(0, False))
return results
This Python solution addresses the problem of determining the number of valid words for each puzzle. The implementation utilizes a trie (prefix tree) to optimize the search for valid words efficiently. Below is a breakdown of how the solution processes the inputs and calculates the desired outputs:
Initialization of Trie Structure:
- A trie is built with its nodes initialized to a list of 26 elements representing the alphabet. Also, a corresponding list
word_terminal_countis used to count word endings (terminals) at each node of the trie.
- A trie is built with its nodes initialized to a list of 26 elements representing the alphabet. Also, a corresponding list
Building the Trie:
- Words are first filtered and processed—converted to a sorted list of unique characters if their length is 7 or fewer.
- Each word is then inserted into the trie. During insertion, if a letter path does not exist in the trie, a new node is created.
- The terminal count is incremented at the node where each word ends, signaling the completion of a valid word insertion.
Defining a Depth-First Search Function:
- A recursive function
searchTrieis defined to navigate through the trie based on the letters of each puzzle. - The function counts valid words by considering whether the first letter of the puzzle is matched.
- As it traverses the puzzle's characters in the trie, it aggregates counts of valid words, utilizing memoization by checking against previously encountered nodes.
- A recursive function
Processing Each Puzzle:
- For each puzzle, the
searchTriefunction is invoked from the root of the trie. The trie is traversed to check against each character of the puzzle, and valid words are counted based on the specified conditions.
- For each puzzle, the
Results Compilation:
- For each puzzle, the number of valid words is appended to a results list, which is then returned.
This method efficiently handles the word and puzzle arrays by leveraging trie data structures to reduce redundant computations and optimize search processes.
No comments yet.