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.

Description Hints 1 Solution Video 17:20

2185. Counting Words With a Given Prefix

Easy84.5% acceptance4 companies

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.

Asked at 4 companies

Google Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Go through each word in words and increment the answer if pref is a prefix of the word.

17:20

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution