Skip to main content
Talentd

Counting Words With a Given Prefix - Solution & Explanation

EasyArrayStringString Matching15 min readAsked at: Microsoft, Meta, Google +1
Practice this problem

Problem Statement

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 Overview

Problem Overview: You are given an array of strings words and a string pref. The task is to count how many words in the array start with the prefix pref. A word is considered valid if its first characters exactly match the prefix.

Approach 1: Iterative Prefix Check (O(n * m) time, O(1) space)

The most direct solution scans every word in the array and checks whether it starts with pref. For each string, compare the first m characters (where m is the length of the prefix). Many languages provide a built‑in operation such as startsWith() or substring comparison, which performs this check efficiently. Since each of the n words may require up to m character comparisons, the time complexity is O(n * m). The algorithm uses constant extra memory O(1). This approach is simple, readable, and usually preferred for small or moderate input sizes involving arrays of strings.

Approach 2: Trie-based Prefix Matching (O(n * m) build, O(m) query, O(n * m) space)

A Trie (prefix tree) stores characters of all words so shared prefixes occupy the same path. Insert every word character by character into the Trie while maintaining a count of words passing through each node. Once built, traverse the nodes corresponding to pref. The stored counter at the final node directly gives the number of words starting with that prefix. Building the structure takes O(n * m) time and space because each character is inserted once. The prefix lookup itself takes O(m). Trie solutions are common in string matching problems when many prefix queries are expected.

Recommended for interviews: The iterative prefix check is what interviewers typically expect for this problem. It demonstrates clean iteration and efficient use of built‑in string operations. The Trie approach shows deeper knowledge of prefix data structures and becomes valuable if the system must answer many prefix queries repeatedly.

Approach 1: Iterative Approach

This approach involves iterating over each word in the list and checking if it starts with the given prefix. This can be achieved using the available string methods in each respective programming language, which allow us to check for a prefix directly. The approach is straightforward and efficient for the given constraints.

This C code defines a function countWordsWithPrefix which counts the number of words in the given array that start with the specified prefix. It uses the strncmp function to compare the start of each word with the prefix.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the number of words and m is the length of the prefix.
Space Complexity: O(1), no extra space needed except for variables.

Try this approach in the editor →

Approach 2: Trie-based Approach

A trie (prefix tree) is a data structure that is very efficient for prefix-based operations. In this approach, we'll first insert all the words into a trie. Then, we'll traverse the trie with the characters of the prefix and count all words that continue from there. Though a bit more complex to implement, this approach is optimal for scenarios where you perform multiple prefix searches.

This C code uses a trie to efficiently store and search the words. Each node in the trie represents a letter and can branch out to the next potential letter in any stored words. After constructing the trie with all the words, we traverse it with the prefix and count all completions that continue from there.

Code

CC++PythonJavaScriptJavaC#

C

C++

Python

JavaScript

Java

C#

Complexity

Time Complexity: O(L + k), where L is the total number of characters in all words and k is the number of characters in the prefix.
Space Complexity: O(ALPHABET_SIZE * L), where ALPHABET_SIZE is 26 for lowercase letters and L is the total number of characters in all words.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach

Time Complexity: O(n * m), where n is the number of words and m is the length of the prefix.
Space Complexity: O(1), no extra space needed except for variables.

Trie-based Approach

Time Complexity: O(L + k), where L is the total number of characters in all words and k is the number of characters in the prefix.
Space Complexity: O(ALPHABET_SIZE * L), where ALPHABET_SIZE is 26 for lowercase letters and L is the total number of characters in all words.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Prefix CheckO(n * m)O(1)Best for a single query over the array. Simple and optimal for most interview scenarios.
Trie-based Prefix MatchingO(n * m) build, O(m) queryO(n * m)Useful when many prefix queries must be answered repeatedly on the same dataset.

Video Solution

Counting Words With a Given Prefix - Leetcode 2185 - Python • NeetCodeIO • 7,889 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Counting Words With a Given Prefix easy or hard?
Counting Words With a Given Prefix is classified as an Easy problem. It focuses on basic string handling, iteration over arrays, and understanding how prefix comparisons work.
How to solve Counting Words With a Given Prefix in O(n)?
Treat the prefix length as a small constant and scan the array once. For every word, check whether the first characters match the prefix using startsWith or direct character comparison. This effectively behaves like an O(n) pass over the list with minimal overhead.
Counting Words With a Given Prefix Python or Java solution
In Python, iterate through the list and use word.startswith(pref). In Java, use word.startsWith(pref) inside a loop. Both implementations run in O(n * m) time and require only constant extra memory.
What is the best approach for Counting Words With a Given Prefix?
The iterative prefix check is the best approach for this problem. Loop through each word and verify whether it starts with the prefix using a built‑in method like startsWith or substring comparison. This runs in O(n * m) time, where n is the number of words and m is the prefix length, and uses O(1) extra space.
What data structure is used in Counting Words With a Given Prefix?
The basic solution uses simple array traversal and string comparison. An alternative approach uses a Trie (prefix tree), which stores characters of all words and allows efficient prefix lookups when multiple queries must be processed.
What is the time complexity of Counting Words With a Given Prefix?
The typical solution runs in O(n * m) time. Each of the n words may require comparing up to m characters of the prefix. Space complexity is O(1) if you only count matches without storing extra structures.
Is Counting Words With a Given Prefix asked at Google, Amazon, or Meta?
Prefix and string matching problems frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem is considered easy, it tests familiarity with string operations and basic iteration patterns commonly used in larger string processing tasks.

Ready to solve this problem?

Practice Counting Words With a Given Prefix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check If a Word Occurs As a Prefix of Any Word in a Sentence

Next

Count Prefixes of a Given String