Counting Words With a Given Prefix solution and explanation
Google
9 more videos on this problem
Counting Words With a Given Prefix - Leetcode 2185 - PythonNeetCodeIO · 17:20 · 7K views
2185. Counting Words With a Given Prefix || LeetCode 2185 || LeetCode Weekly Contest 282Bro Coders · 4:30 · 1K views
2185. Counting Words With a Given Prefix | LeetCode Daily Challenge | DSA | ShashCode | JavaShashCode · 5:51 · 1K views
Leetcode | 2185. Counting Words With a Given Prefix | Easy | Java SolutionDeveloper Docs · 4:40 · 514 views
2185. Counting Words With a Given Prefix (Leetcode Easy)Programming Live with Larry · 1:50 · 416 views
Leetcode Weekly 282 | 1st Problem | 2185. Counting Words With a Given PrefixcodingMohan · 3:31 · 272 views
Counting Words With a Given Prefix - LeetCode 2185 - Javaalgobest - Computer Science · 2:43 · 124 views
LeetCode 2185 Counting Words With a Given Prefix | Easy | String Matching | Asked in GoogleCode Harmony · 5:46 · 117 views
Counting Words With a Given Prefix | LeetCode 2185 | Built-In Methods | Java Code | Developer CoderDeveloper Coder · 2:32 · 46 views
Counting Words With a Given Prefix - Leetcode 2185 - JavaCode With K5KC · 3:03 · 44 views
The problem
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 <= 1001 <= words[i].length, pref.length <= 100words[i]andprefconsist 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.
def count_words_with_prefix(words, pref):
count = 0
for word in words:
if word.startswith(pref):
count += 1
return count
words = ["pay", "attention", "practice", "attend"]
pref = "at"
print(count_words_with_prefix(words, pref))import java.util.*;
public class Solution {
public static int countWordsWithPrefix(String[] words, String pref) {
int count = 0;
for (String word : words) {
if (word.startsWith(pref)) {
count++;
}
}
return count;
}
public static void main(String[] args) {
String[] words = {"pay", "attention", "practice", "attend"};
String pref = "at";
System.out.println(countWordsWithPrefix(words, pref));
}
}#include <iostream>
#include <vector>
int countWordsWithPrefix(const std::vector<std::string>& words, const std::string& pref) {
int count = 0;
for (const std::string& word : words) {
if (word.find(pref) == 0) {
count++;
}
}
return count;
}
int main() {
std::vector<std::string> words = {"pay", "attention", "practice", "attend"};
std::string pref = "at";
std::cout << countWordsWithPrefix(words, pref) << std::endl;
return 0;
}function countWordsWithPrefix(words, pref) {
let count = 0;
for (const word of words) {
if (word.startsWith(pref)) {
count++;
}
}
return count;
}
const words = ["pay", "attention", "practice", "attend"];
const pref = "at";
console.log(countWordsWithPrefix(words, pref));#include <stdio.h>
#include <string.h>
int countWordsWithPrefix(char *words[], int wordsSize, char *pref) {
int count = 0;
int prefLen = strlen(pref);
for (int i = 0; i < wordsSize; i++) {
if (strncmp(words[i], pref, prefLen) == 0) {
count++;
}
}
return count;
}
int main() {
char *words[] = {"pay", "attention", "practice", "attend"};
char *pref = "at";
int result = countWordsWithPrefix(words, 4, pref);
printf("%d\n", result);
return 0;
}using System;
class Solution {
public static int CountWordsWithPrefix(string[] words, string pref) {
int count = 0;
foreach (var word in words) {
if (word.StartsWith(pref)) {
count++;
}
}
return count;
}
public static void Main(string[] args) {
string[] words = {"pay", "attention", "practice", "attend"};
string pref = "at";
Console.WriteLine(CountWordsWithPrefix(words, pref));
}
}This Python code implements the count_words_with_prefix function, which uses the startswith method to check if each string in the list begins with the specified prefix.
Time Complexity: O(n * m), where n is the number of words and m is the length of the prefix.
Space Complexity: O(1), with minimal extra space used.
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.
class TrieNode:
def __init__(self):
self.children = {}
self.word_count = 0
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.word_count += 1
def countWordsWithPrefix(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return 0
node = node.children[char]
return self.count_words(node)
def count_words(self, node):
count = node.word_count
for child in node.children.values():
count += self.count_words(child)
return count
words = ["pay", "attention", "practice", "attend"]
trie = Trie()
for word in words:
trie.insert(word)
print(trie.countWordsWithPrefix("at"))import java.util.HashMap;
class TrieNode {
HashMap<Character, TrieNode> children = new HashMap<>();
int wordCount = 0;
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
if (!node.children.containsKey(ch)) {
node.children.put(ch, new TrieNode());
}
node = node.children.get(ch);
}
node.wordCount++;
}
public int countWordsWithPrefix(String prefix) {
TrieNode node = root;
for (char ch : prefix.toCharArray()) {
if (!node.children.containsKey(ch)) {
return 0;
}
node = node.children.get(ch);
}
return countWords(node);
}
private int countWords(TrieNode node) {
int count = node.wordCount;
for (TrieNode child : node.children.values()) {
count += countWords(child);
}
return count;
}
}
public class Solution {
public static void main(String[] args) {
String[] words = {"pay", "attention", "practice", "attend"};
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
System.out.println(trie.countWordsWithPrefix("at"));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
class TrieNode {
public:
std::unordered_map<char, TrieNode*> children;
int wordCount;
TrieNode() : wordCount(0) {}
};
class Trie {
public:
TrieNode* root;
Trie() { root = new TrieNode(); }
void insert(const std::string& word) {
TrieNode* node = root;
for (char ch : word) {
if (!node->children.count(ch))
node->children[ch] = new TrieNode();
node = node->children[ch];
}
node->wordCount++;
}
int countWordsWithPrefix(const std::string& prefix) {
TrieNode* node = root;
for (char ch : prefix) {
if (!node->children.count(ch))
return 0;
node = node->children[ch];
}
return countWords(node);
}
private:
int countWords(TrieNode* node) {
int count = node->wordCount;
for (auto pair : node->children)
count += countWords(pair.second);
return count;
}
};
int main() {
std::vector<std::string> words = {"pay", "attention", "practice", "attend"};
Trie trie;
for (const std::string& word : words) {
trie.insert(word);
}
std::cout << trie.countWordsWithPrefix("at") << std::endl;
return 0;
}class TrieNode {
constructor() {
this.children = {};
this.wordCount = 0;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.wordCount++;
}
countWordsWithPrefix(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node.children[char]) {
return 0;
}
node = node.children[char];
}
return this.countWords(node);
}
countWords(node) {
let count = node.wordCount;
for (let child of Object.values(node.children)) {
count += this.countWords(child);
}
return count;
}
}
const words = ["pay", "attention", "practice", "attend"];
const trie = new Trie();
for (const word of words) {
trie.insert(word);
}
console.log(trie.countWordsWithPrefix("at"));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET_SIZE 26
struct TrieNode {
struct TrieNode *children[ALPHABET_SIZE];
int wordCount;
};
struct TrieNode *getNode(void) {
struct TrieNode *node = (struct TrieNode *)malloc(sizeof(struct TrieNode));
node->wordCount = 0;
for (int i = 0; i < ALPHABET_SIZE; i++)
node->children[i] = NULL;
return node;
}
void insert(struct TrieNode *root, const char *word) {
struct TrieNode *node = root;
while (*word) {
int index = *word - 'a';
if (!node->children[index])
node->children[index] = getNode();
node = node->children[index];
word++;
}
node->wordCount++; // Marks end of word
}
int countPrefix(struct TrieNode *root, const char *prefix) {
int count = 0;
struct TrieNode *node = root;
while (*prefix) {
int index = *prefix - 'a';
if (!node->children[index])
return 0;
node = node->children[index];
prefix++;
}
count += node->wordCount;
return count;
}
void countAllWords(struct TrieNode *node, int *count) {
if (!node)
return;
*count += node->wordCount;
for (int i = 0; i < ALPHABET_SIZE; i++)
if (node->children[i])
countAllWords(node->children[i], count);
}
int countWordsWithPrefix(struct TrieNode *root, const char *pref) {
int count = countPrefix(root, pref);
if (count == 0)
return 0;
struct TrieNode *node = root;
while (*pref) {
int index = *pref - 'a';
if (!node->children[index])
return 0;
node = node->children[index];
pref++;
}
countAllWords(node, &count);
return count;
}
int main() {
char *words[] = {"pay", "attention", "practice", "attend"};
struct TrieNode *root = getNode();
for (int i = 0; i < 4; i++)
insert(root, words[i]);
printf("%d\n", countWordsWithPrefix(root, "at"));
return 0;
}using System;
using System.Collections.Generic;
class TrieNode {
public Dictionary<char, TrieNode> Children { get; } = new Dictionary<char, TrieNode>();
public int WordCount { get; set; } = 0;
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void Insert(string word) {
var node = root;
foreach (var ch in word) {
if (!node.Children.ContainsKey(ch)) {
node.Children[ch] = new TrieNode();
}
node = node.Children[ch];
}
node.WordCount++;
}
public int CountWordsWithPrefix(string prefix) {
var node = root;
foreach (var ch in prefix) {
if (!node.Children.ContainsKey(ch)) {
return 0;
}
node = node.Children[ch];
}
return CountWords(node);
}
private int CountWords(TrieNode node) {
int count = node.WordCount;
foreach (var child in node.Children.Values) {
count += CountWords(child);
}
return count;
}
}
class Solution {
public static void Main(string[] args) {
string[] words = {"pay", "attention", "practice", "attend"};
var trie = new Trie();
foreach (var word in words) {
trie.Insert(word);
}
Console.WriteLine(trie.CountWordsWithPrefix("at"));
}
}This Python solution builds on the TrieNode structure to save all the words. After constructing the tree, the method countWordsWithPrefix efficiently finds the node representing all words continuing from the prefix and counts them recursively.
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(L), accounting for all characters stored in the trie.
Approach 3: Default Approach
function prefixCount(words: string[], pref: string): number {
return words.reduce((r, s) => (r += s.startsWith(pref) ? 1 : 0), 0);
}func prefixCount(words []string, pref string) (ans int) {
for _, w := range words {
if strings.HasPrefix(w, pref) {
ans++
}
}
return
}impl Solution {
pub fn prefix_count(words: Vec<String>, pref: String) -> i32 {
words.iter().filter(|s| s.starts_with(&pref)).count() as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n * m), where n is the number of words and m is the length of the prefix. |
| 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. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Prefix Check | O(n * m) | O(1) | Best for a single query over the array. Simple and optimal for most interview scenarios. |
| Trie-based Prefix Matching | O(n * m) build, O(m) query | O(n * m) | Useful when many prefix queries must be answered repeatedly on the same dataset. |
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.