Counting Words With a Given Prefix — Problem & Solution
Counting Words With a Given Prefix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Counting Words With a Given Prefix is an easy coding problem on arrays, strings and string matching, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, String Matching
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array of strings words and a string pref.
Return the number of strings in words that have pref as a prefix — that is, that begin with pref. A string is a prefix of itself.
Example 1
Input: words = ["kairo","kai","code","kaizen"], pref = "kai"
Output: 3
Explanation: `"kairo"`, `"kai"` and `"kaizen"` start with `"kai"`.
Example 2
Input: words = ["leetcode","win","loops","success"], pref = "code"
Output: 0
Explanation: `"code"` appears inside `"leetcode"` but not at its start.
Example 3
Input: words = ["abc"], pref = "abcd"
Output: 0
Explanation: A prefix cannot be longer than the word.
Constraints
1 <= words.length <= 1001 <= words[i].length, pref.length <= 100words[i] and pref consist of lowercase English letters
Hints for Counting Words With a Given Prefix
Hint 1
Each word can be checked on its own.
Hint 2
A word has the prefix when it is at least as long as
prefand its first|pref|characters equalpref.Hint 3
Most languages have a built-in
startsWithfor exactly this.
How to solve Counting Words With a Given Prefix
Test every word with a prefix comparison and count the matches.
Approach
- Set
count = 0. - For each word, if it starts with
pref, incrementcount. - Return
count.
Complexity
- Time —
O(n · |pref|) - Space —
O(1)
Pitfalls
- A substring match anywhere in the word is not enough — it must be at the start.
- Guard the length when comparing manually: a word shorter than
prefnever matches.
Reference solution
Python
from typing import List
def prefixCount(words: List[str], pref: str) -> int:
return sum(1 for w in words if w.startswith(pref))Java
public static int prefixCount(String[] words, String pref) {
int count = 0;
for (String w : words) if (w.startsWith(pref)) count++;
return count;
}C++
int prefixCount(vector<string>& words, string pref) {
int count = 0;
for (const string& w : words) {
if (w.size() >= pref.size() && w.compare(0, pref.size(), pref) == 0) count++;
}
return count;
}JavaScript
var prefixCount = function(words, pref) {
var count = 0;
for (var i = 0; i < words.length; i++) {
if (words[i].substring(0, pref.length) === pref) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.