Counting Words With a Given Prefix

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 <= 100
• 1 <= words[i].length, pref.length <= 100
• words[i] and pref consist 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:

1. Initialize a counter to keep track of how many strings match the prefix criteria.
2. Loop through each string in the words array.
   • For each string, check if the string starts with the substring pref.
   • This can be efficiently checked using string methods that evaluate prefixes.
3. If a string does start with pref, increment the counter.
4. After processing all strings in the array, the counter will contain the number of strings that start with the given prefix.
5. 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 words array, i.e., O(n), where n is 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

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;
        }
    };
};