Problem Statement
Given an array of strings named words and another string called pref, the task is to determine the number of strings within the words array that start with the substring pref. The substring referred to as pref must be a prefix in the string from the words array. By the definition of a prefix in string handling, a prefix is identified as the beginning part of a string that directly matches another string or substring. The main goal is to return a count of such strings where pref acts as a prefix.
Examples
Example 1
Input:
words = ["pay","attention","practice","attend"], `pref` = "at"
Output:
2
Explanation:
The 2 strings that contain "at" as a prefix are: "attention" and "attend".
Example 2
Input:
words = ["vultr","win","loops","success"], `pref` = "code"
Output:
0
Explanation:
There are no strings that contain "code" as a prefix.
Constraints
1 <= words.length <= 1001 <= words[i].length, pref.length <= 100words[i]andprefconsist of lowercase English letters.
Approach and Intuition
The problem requires us to count the strings that start with a specific substring (pref). Here's how we can approach this problem step-by-step:
- Initialize a counter to keep track of how many strings match the prefix criteria.
- Loop through each string in the
wordsarray.- For each string, check if the string starts with the substring
pref. - This can be efficiently checked using string methods that evaluate prefixes.
- For each string, check if the string starts with the substring
- If a string does start with
pref, increment the counter. - After processing all strings in the array, the counter will contain the number of strings that start with the given prefix.
- Return this counter.
Key considerations based on the constraints are:
- The length of each string and the prefix can go up to 100 characters, which means the prefix checking will run efficiently even with the maximum constraints.
- The loop to check each word runs linearly with respect to the size of the
wordsarray, i.e.,O(n), wherenis the number of words.
This approach is straightforward due to the direct application of string prefix checks available in most programming languages, ensuring that we can perform the operation swiftly without needing complex algorithms. Given the constraints, this method will perform efficiently.
Solutions
- C++
- Java
- Python
class Solution {
public:
int countPrefixInWords(vector<string>& words, string prefix) {
TrieStructure trie;
// Insert each word into the trie
for (string& word : words) {
trie.insertWord(word);
}
return trie.getPrefixCount(prefix);
}
private:
class TrieStructure {
struct TrieNode {
vector<TrieNode*> children;
int prefixCount;
TrieNode() : children(26, nullptr), prefixCount(0) {}
};
TrieNode* root;
public:
TrieStructure() { root = new TrieNode(); }
// Insert a word into the trie and update prefix count
void insertWord(string& word) {
TrieNode* node = root;
for (char ch : word) {
if (node->children[ch - 'a'] == nullptr) {
node->children[ch - 'a'] = new TrieNode();
}
node = node->children[ch - 'a'];
node->prefixCount++;
}
}
// Get the number of words in the trie that start with the given prefix
int getPrefixCount(string& prefix) {
TrieNode* node = root;
for (char ch : prefix) {
if (node->children[ch - 'a'] == nullptr) {
return 0;
}
node = node->children[ch - 'a'];
}
return node->prefixCount;
}
};
};
This solution addresses the problem of counting words with a specific prefix using a trie data structure in C++. The provided C++ class Solution includes a private nested class TrieStructure that handles trie operations.
The countPrefixInWords function operates as follows:
- Initialize an instance of
TrieStructure. - Insert each word from the vector
wordsinto the trie. - Calculate and return the count of how many words start with the specified prefix using
getPrefixCount.
The TrieStructure class consists of:
- A nested structure
TrieNode, representing each node in the trie. Each node maintains a vector for child nodes and an integerprefixCountto track the number of words sharing the same prefix up to that node. - Two primary functions:
insertWord, which adds words to the trie and increments theprefixCountat each node affected by the insertion of the word.getPrefixCount, which traverses the trie based on the given prefix and returns the count at the terminal node of the prefix.
This implementation ensures efficient counting of words matching a specific prefix, leveraging the trie's ability to store and retrieve prefixes effectively.
class Solution {
public int prefixCount(String[] words, String pref) {
int totalCount = 0;
PrefixTree prefixTree = new PrefixTree();
// Iterating through each word and adding to PrefixTree
for (String word : words) {
prefixTree.insertWord(word);
}
return prefixTree.getPrefixCount(pref);
}
private class PrefixTree {
class TrieNode {
TrieNode[] children;
int prefixCount;
TrieNode() {
children = new TrieNode[26];
prefixCount = 0;
}
}
TrieNode root;
PrefixTree() {
root = new TrieNode();
}
// Inserts a word into the PrefixTree and increments prefixes
public void insertWord(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (current.children[ch - 'a'] == null) {
current.children[ch - 'a'] = new TrieNode();
}
current = current.children[ch - 'a'];
current.prefixCount++; // Update prefixCount for this node
}
}
// Returns the count of words having the given prefix
public int getPrefixCount(String prefix) {
TrieNode current = root;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
if (current.children[ch - 'a'] == null) {
return 0; // No words with such prefix
}
current = current.children[ch - 'a'];
}
return current.prefixCount; // Count at terminal node of prefix
}
}
}
Manage the complexity of counting words that begin with a specific prefix in Java by utilizing a specialized data structure called a PrefixTree or Trie. The approach involves creating an inner class to represent each node within the tree and a primary class that manages the overall processes within this tree.
Implement the TrieNode class:
- Each node has an array that represents possible child nodes corresponding to letters of the alphabet.
- Include an integer to count the number of words passing through this node with the respective prefix.
Construct the PrefixTree class:
- Initialize a root which represents the starting point of the Trie.
Define two main functionalities on PrefixTree:
insertWord(String word): This method adds a word to the tree. For every character in the word, navigate through the tree or create new nodes if necessary, updating the prefix count at each node.getPrefixCount(String prefix): This searches the tree for the given prefix and returns the number of times the prefix appears as the start of any word in the tree.
Utilize the
prefixCountmethod:- This method incorporates the PrefixTree to count words in the input array that begin with a given prefix.
By effectively structuring your data and implementing efficient search and insert operations, this Java code effectively handles the counting of prefixes, optimizing both time and space complexity.
class Solution:
def countPrefixUtil(self, wordList: List[str], prefix: str) -> int:
trieStructure = self._Trie()
# Insert each word into the Trie structure
for word in wordList:
trieStructure._insert_word(word)
return trieStructure._get_prefix_count(prefix)
class _Trie:
# Individual Trie node structure
class _Node:
def __init__(self):
# Maintain links to child nodes
self.children = [None] * 26
# Track the number of strings with this prefix
self.prefixCount = 0
def __init__(self):
self.root = self._Node()
# Function to add a word into the Trie
def _insert_word(self, word: str) -> None:
node = self.root
for letter in word:
index = ord(letter) - ord("a")
if node.children[index] is None:
node.children[index] = self._Node()
node = node.children[index]
node.prefixCount += 1 # Update the prefix count
# Compute the number of words with the given prefix
def _get_prefix_count(self, prefix: str) -> int:
node = self.root
for letter in prefix:
index = ord(letter) - ord("a")
if node.children[index] is None:
return 0 # The prefix doesn't exist
node = node.children[index]
return node.prefixCount # Return the count of words with the prefix
This article outlines a solution for counting the number of words in a list that start with a given prefix. This is achieved using Python and the Trie data structure within a Solution class.
- The function
countPrefixUtilaccepts a list of words and a prefix. It uses a nested_Trieclass for efficiently handling the prefix operations. - Initialize and populate the
_Triewith words from the list insidecountPrefixUtil. - Call
_get_prefix_counton the Trie with the specified prefix to retrieve the count of words starting with that prefix.
The _Trie data structure includes:
- An inner
_Nodeclass representing each Trie node, which:- Stores links to child nodes using a list of 26 elements (one for each letter of the alphabet).
- Keeps a count of how many words have the node as their prefix (
prefixCount).
- A method
_insert_wordto insert each word into the Trie. This method updates theprefixCountfor each node affected by the insertion. - A method
_get_prefix_countto determine how many words in the Trie start with a given prefix. This method iterates through each character in the prefix, checking the corresponding child in the Trie.
This setup ensures efficient querying and manipulation of prefix-related data, utilizing the properties of the Trie to minimize the need for redundant string comparisons.
No comments yet.