Counting Words With a Given Prefix

Difficulty: Easy | Acceptance: 84.40% | Paid: No Topics: Array, String, String Matching

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

Return the number of strings in words that start with pref.

A string s starts with pref if s is equal to pref concatenated with some string (possibly empty).

• Examples
• Constraints
• Approach 1: Iterative Comparison
• Approach 2: Built-in String Methods

Examples

Example 1:

Input: words = ["pay","attention","practice","attend"], pref = "at"
Output: 2
Explanation: "pay" does not start with "at", so it is not counted.
"attention" and "attend" start with "at", so they are counted.

Example 2:

Input: words = ["leetcode","win","loops","success"], pref = "code"
Output: 0
Explanation: None of the strings start with "code".

Constraints

1 <= words.length <= 100
1 <= words[i].length, pref.length <= 100
words[i] and pref consist of lowercase English letters.

Approach 1: Iterative Comparison

Intuition We can manually check each word by comparing characters one by one to see if they match the prefix.

Steps

• Initialize a counter to 0.
• Iterate through each word in the array.
• If the word’s length is less than the prefix length, skip it.
• Loop through the characters of the prefix and compare them with the corresponding characters in the word.
• If all characters match, increment the counter.

class Solution:
    def prefixCount(self, words: list[str], pref: str) -> int:
        count = 0
        p_len = len(pref)
        for w in words:
            if len(w) >= p_len:
                match = True
                for i in range(p_len):
                    if w[i] != pref[i]:
                        match = False
                        break
                if match:
                    count += 1
        return count

Complexity

• Time: O(N * M), where N is the number of words and M is the length of the prefix.
• Space: O(1)
• Notes: This approach is fundamental and works in any programming environment without relying on standard library helpers.

Approach 2: Built-in String Methods

Intuition Most modern programming languages provide optimized built-in methods to check if a string starts with a specific substring.

Steps

• Initialize a counter to 0.
• Iterate through each word in the array.
• Use the language’s built-in “starts with” function to check if the word begins with the prefix.
• If true, increment the counter.

class Solution:
    def prefixCount(self, words: list[str], pref: str) -> int:
        return sum(1 for w in words if w.startswith(pref))

Complexity

• Time: O(N * M), where N is the number of words and M is the length of the prefix.
• Space: O(1)
• Notes: While the time complexity is theoretically the same as the iterative approach, built-in methods are often highly optimized and result in cleaner, more readable code.