Abstract / Summary

Count how many words in a list start with a specified prefix.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 84% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• String
• String Matching

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method prefixCount. The method receives a list of strings (words) and a prefix string (pref). It returns the number of elements in words that begin with the given prefix. The logic is expressed in a single return statement that combines iteration, a prefix test, and aggregation.

Key Steps

The core operation consists of three conceptual stages: iteration over the input collection, evaluation of the prefix condition, and accumulation of matching items. The following snippet isolates the essential expression used for these stages:

sum(1 for w in words if w.startswith(pref))

Iteration is performed by the generator expression for w in words, which yields each word one at a time without creating an intermediate container.

Condition checking relies on the built-in string method startswith(pref). This method is implemented in C and performs a direct memory comparison of the prefix against the beginning of the string, providing a fast path for the common case where the prefix does not match.

Accumulation is achieved by sum, which adds the value 1 for every word that satisfies the condition, producing the final count.

Edge Cases Handled

When the input list words is empty, the generator produces no elements, and sum returns 0. This correctly reflects that there are no words matching any prefix.

If the prefix pref is an empty string, startswith('') is defined to return True for any string, including the empty string itself. Consequently, the method counts every element in words, which aligns with the mathematical definition that every string starts with the empty prefix.

When the length of pref exceeds the length of a particular word, startswith immediately evaluates to False without scanning the entire word, ensuring that such words are excluded from the count.

The implementation also gracefully handles cases where words contains duplicate entries; each occurrence is evaluated independently, and the count reflects the total number of matching instances.

Performance Optimizations

The use of a generator expression inside sum avoids materializing a list of boolean values or intermediate integers, thereby reducing memory pressure especially for large input arrays.

The reliance on the native startswith method leverages low-level optimizations present in the Python runtime, such as early termination when the prefix cannot possibly match and direct byte-wise comparison for ASCII strings.

By aggregating the result with a single pass through the data, the algorithm eliminates the need for multiple traversals or auxiliary data structures, delivering a streamlined execution path.

Imagine a big box filled with many different word cards. Each card has a word written on it. Now, suppose someone gives a special starting piece of a word, like a tiny secret code. The goal is to look through every single card in the box to see if the word starts with that exact secret code. Every time a card matches, a point is added to a scoreboard. By the time every card has been checked, the scoreboard shows exactly how many words started with that secret code.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java					C	Go	Rust	TS
	Progiez	C++	Python	Java
github	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	DimitrisJim								C
	fartem				Ruby
	fsq	C++
	JoshCrozier					JS
	lkwq007		Python
	Shamik07						Dart
	suxrobGM							C#
	trung-hn		Python
	varunu28			Java
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
Shamik07	Dart
suxrobGM	C#
trung-hn	Python
varunu28	Java
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality