LeetCode 2185 - Counting Words With a Given Prefix

The problem gives us two inputs: - An array of strings called words - A string called pref We must count how many strings inside words start with the string pref. A prefix means the beginning portion of a string.

leetcodeeasyarraystringstring-matching

LeetCode Problem 2185

Difficulty: 🟢 Easy
Topics: Array, String, String Matching

Solution

Problem Understanding

The problem gives us two inputs:

  • An array of strings called words
  • A string called pref

We must count how many strings inside words start with the string pref.

A prefix means the beginning portion of a string. For example:

  • "at" is a prefix of "attention"
  • "pay" is a prefix of "pay"
  • "code" is not a prefix of "leetcode" because "leetcode" does not start with "code"

The task is therefore straightforward:

  1. Examine every word in the array.
  2. Check whether the word begins with pref.
  3. Count how many words satisfy this condition.
  4. Return the final count.

The constraints are small:

  • At most 100 words
  • Each word length is at most 100
  • The prefix length is at most 100

These constraints tell us that performance is not a major concern. Even a direct character-by-character comparison is completely acceptable because the total amount of data is tiny.

An important detail is that the prefix must appear at the start of the word. It is not enough for the substring to appear somewhere in the middle.

For example:

  • "attend" starts with "at", valid
  • "practice" contains "at" in the middle, invalid

The problem also guarantees that:

  • All strings are lowercase English letters
  • Every string has length at least 1
  • The prefix is non-empty

These guarantees simplify the implementation because we do not need to handle empty strings or invalid input.

Some important edge cases include:

  • No words match the prefix
  • Every word matches the prefix
  • The prefix is longer than some words
  • A word is exactly equal to the prefix
  • The array contains only one word

A correct solution must handle all of these situations consistently.

Approaches

Brute Force Approach

The brute-force method compares the prefix against each word character by character.

For every word:

  1. First check whether the word is long enough to contain the prefix.
  2. Compare each character of the prefix with the corresponding character in the word.
  3. If all characters match, increment the answer.

This works because a string starts with a prefix exactly when every prefix character matches the corresponding character at the beginning of the word.

Although this method is fully correct, it requires manually iterating through characters. The implementation is more verbose than necessary, and modern programming languages already provide optimized prefix-checking functions.

The worst-case complexity is still acceptable because the constraints are small, but we can write a cleaner and more readable solution.

Optimal Approach

The key observation is that most languages already include a built-in method for checking prefixes.

In Python, we can use:

word.startswith(pref)

In Go, we can use:

strings.HasPrefix(word, pref)

These functions directly express the intent of the problem and internally perform the necessary comparisons efficiently.

The algorithm becomes:

  1. Iterate through every word.
  2. Check whether it starts with pref.
  3. Count the matches.

This is both simple and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × m) O(1) Manually compares characters for every word
Optimal O(n × m) O(1) Uses built-in prefix checking functions

Here:

  • n is the number of words
  • m is the length of the prefix

Algorithm Walkthrough

  1. Initialize a variable called count to 0.

This variable keeps track of how many words begin with the given prefix. 2. Iterate through each word in the words array.

We must inspect every word because any of them could match the prefix. 3. For the current word, check whether it starts with pref.

In Python, this is done using word.startswith(pref).

In Go, this is done using strings.HasPrefix(word, pref).

These functions compare the beginning of the word with the prefix. 4. If the word starts with the prefix, increment count.

Every successful match contributes exactly one to the final answer. 5. After processing all words, return count.

At this point, the counter represents the total number of matching words.

Why it works

The algorithm examines every word exactly once and checks whether the prefix matches the beginning of that word. Since every valid matching word increments the counter exactly once, and every non-matching word contributes nothing, the final count is precisely the number of words containing pref as a prefix.

Python Solution

from typing import List

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        count = 0

        for word in words:
            if word.startswith(pref):
                count += 1

        return count

The implementation begins by initializing count to zero. This variable stores the number of matching words.

Next, the code loops through every word in the words array. For each word, it uses Python's built-in startswith() method to determine whether the word begins with pref.

If the condition is true, the counter is incremented.

Finally, after all words have been checked, the function returns the accumulated count.

The implementation directly follows the algorithm described earlier and uses Python's built-in string functionality to keep the solution concise and readable.

Go Solution

package main

import "strings"

func prefixCount(words []string, pref string) int {
    count := 0

    for _, word := range words {
        if strings.HasPrefix(word, pref) {
            count++
        }
    }

    return count
}

The Go solution follows the same logic as the Python version. The main difference is that Go requires importing the strings package to use strings.HasPrefix.

The loop iterates through the slice using Go's range syntax. Since the constraints are very small, integer overflow is not a concern. The solution uses constant extra space and handles all edge cases naturally.

Worked Examples

Example 1

Input:

words = ["pay","attention","practice","attend"]
pref = "at"

We start with:

count = 0
Current Word Starts With "at"? Count After Processing
"pay" No 0
"attention" Yes 1
"practice" No 1
"attend" Yes 2

Final answer:

2

Example 2

Input:

words = ["leetcode","win","loops","success"]
pref = "code"

Initial state:

count = 0
Current Word Starts With "code"? Count After Processing
"leetcode" No 0
"win" No 0
"loops" No 0
"success" No 0

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n × m) Each word may compare up to m prefix characters
Space O(1) Only a counter variable is used

The algorithm processes every word once. For each word, the prefix comparison may examine up to m characters, where m is the length of pref.

No additional data structures proportional to the input size are created, so the extra space usage remains constant.

Test Cases

from typing import List

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        count = 0

        for word in words:
            if word.startswith(pref):
                count += 1

        return count

solution = Solution()

assert solution.prefixCount(
    ["pay", "attention", "practice", "attend"], "at"
) == 2  # provided example with two matches

assert solution.prefixCount(
    ["leetcode", "win", "loops", "success"], "code"
) == 0  # provided example with no matches

assert solution.prefixCount(
    ["apple", "app", "application"], "app"
) == 3  # every word matches

assert solution.prefixCount(
    ["dog", "cat", "bird"], "z"
) == 0  # no word starts with prefix

assert solution.prefixCount(
    ["a"], "a"
) == 1  # single word equal to prefix

assert solution.prefixCount(
    ["ab", "abc", "abcd"], "abc"
) == 2  # prefix longer than some words

assert solution.prefixCount(
    ["hello", "he", "hero"], "he"
) == 3  # exact word and longer words both count

assert solution.prefixCount(
    ["test"], "testing"
) == 0  # prefix longer than the word

assert solution.prefixCount(
    ["aaa", "aa", "a"], "a"
) == 3  # short prefix matching all words

assert solution.prefixCount(
    ["prefix", "suffix", "prelude"], "pre"
) == 2  # multiple matches among mixed words
Test Why
["pay","attention","practice","attend"], "at" Validates normal matching behavior
["leetcode","win","loops","success"], "code" Validates zero matches
["apple","app","application"], "app" Ensures all words can match
["dog","cat","bird"], "z" Tests completely absent prefix
["a"], "a" Tests smallest valid input
["ab","abc","abcd"], "abc" Tests words shorter than prefix
["hello","he","hero"], "he" Ensures exact equality counts as a prefix
["test"], "testing" Tests prefix longer than word
["aaa","aa","a"], "a" Tests single-character prefix
["prefix","suffix","prelude"], "pre" Tests mixed matching and non-matching words

Edge Cases

Prefix Longer Than the Word

A common source of bugs is attempting to compare characters beyond the end of a shorter word. For example:

word = "ab"
pref = "abcd"

The word cannot possibly start with the prefix because it is shorter. The built-in prefix functions automatically handle this safely and correctly return False.

Word Exactly Equal to the Prefix

Some incorrect implementations only count words that are strictly longer than the prefix. However, a string is always considered to start with itself.

For example:

word = "app"
pref = "app"

This should count as a valid match. Both implementations correctly treat equality as a successful prefix match.

No Matching Words

Another important case occurs when none of the words begin with the prefix. The algorithm must still correctly return 0 rather than an uninitialized value or incorrect count.

For example:

words = ["dog", "cat"]
pref = "z"

Since no word satisfies the condition, the counter never increments, and the final returned value remains 0.