2185. Counting Words With a Given Prefix

You are given an array of strings words and a string pref.

Return the number of strings in words that contain pref as a prefix.

A prefix of a string s is any leading contiguous substring of s.

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 = ["leetcode","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 01:

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    int prefixCount(vector<string>& words, string prefix) {
        int wordCount = words.size();  // Number of words in the input
        int prefixLength = prefix.length();  // Length of the prefix
        int matchingCount = 0;  // Counter for words starting with the prefix
        
        for (int i = 0; i < wordCount; ++i) {
            if (words[i].length() >= prefixLength) {  // Ensure the word is at least as long as the prefix
                string wordPrefix = words[i].substr(0, prefixLength);  // Extract the prefix from the word
                if (wordPrefix == prefix) {  // Check if the prefix matches
                    ++matchingCount;
                }
            }
        }
        
        return matchingCount;  // Return the total count of matching words
    }
};

class Solution:
    def prefixCount(self, words: list[str], prefix: str) -> int:
        wordCount = len(words)  # Number of words in the input
        prefixLength = len(prefix)  # Length of the prefix
        matchingCount = 0  # Counter for words starting with the prefix
        
        for word in words:
            if len(word) >= prefixLength:  # Ensure the word is at least as long as the prefix
                wordPrefix = word[:prefixLength]  # Extract the prefix from the word
                if wordPrefix == prefix:  # Check if the prefix matches
                    matchingCount += 1
        
        return matchingCount  # Return the total count of matching words

Time Complexity:

• Iterating Over Words:

  The loop iterates through all words in the input, taking \( O(n) \), where \( n \) is the number of words.

• Prefix Extraction:

  For each word, extracting the prefix using substr takes \( O(m) \), where \( m \) is the length of the prefix.

• Overall Time Complexity:

  \( O(n \cdot m) \).

Space Complexity:

• Prefix Storage:

  Extracted prefixes temporarily occupy \( O(m) \) space, as only one prefix is stored at a time.

• Input Storage:

  The input words and prefix do not require additional space, as they are read-only.

• Overall Space Complexity:

  \( O(m) \).