Count Prefixes of a Given String solution and explanation
Google
9 more videos on this problem
2255 Count Prefixes of a Given String | Zero to FAANG | Assignment Solution | Leetcode | StriverProgrammers Zone · 10:26 · 929 views
[Java / C++] Count Prefixes of a Given String | LEETCODE - 2255 | Easy solutionhi-malik · 4:56 · 714 views
2255. Count Prefixes of a Given String (Leetcode Easy)Programming Live with Larry · 2:22 · 338 views
Count Prefixes of a Given String - LeetCode 2255 - Java Solutionalgobest - Computer Science · 2:29 · 269 views
LeetCode 2255 | Count Prefixes of a Given String | String | JavaSleepy Cracker · 1:59 · 151 views
2255. Count Prefixes of a Given String with Python | Leetcode with pythonArsalan Ahmed · 5:07 · 132 views
Leetcode Biweekly-contest-77 - Count Prefixes of a Given StringPrakhar Agrawal · 4:10 · 126 views
2255. Count Prefixes of a Given String with JavaScript | Leetcode with JavaScriptArsalan Ahmed · 4:26 · 57 views
Day 387: LeetCode Problem 2255. Count Prefixes of a Given String - SwiftiOSxBank · 8:36 · 53 views
Leetcode Python - Easy - Count Prefixes of Given String (Linear - Single Pointer)ShipItParrot · 5:14 · 62 views
The problem
You are given a string array words and a string s, where words[i] and s comprise only of lowercase English letters.
Return the number of strings in words that are a prefix of s.
A prefix of a string is a substring that occurs at the beginning of the string. A substring is a contiguous sequence of characters within a string.
Example 1:
Input: words = ["a","b","c","ab","bc","abc"], s = "abc" Output: 3 Explanation: The strings in words which are a prefix of s = "abc" are: "a", "ab", and "abc". Thus the number of strings in words which are a prefix of s is 3.
Example 2:
Input: words = ["a","a"], s = "aa" Output: 2 Explanation: Both of the strings are a prefix of s. Note that the same string can occur multiple times in words, and it should be counted each time.
Constraints:
1 <= words.length <= 10001 <= words[i].length, s.length <= 10words[i]andsconsist of lowercase English letters only.
Approach overview
Problem Overview: You receive a list of words and a target string s. The task is to count how many words in the array are prefixes of s. A word is a prefix if it matches the beginning portion of the string exactly.
The challenge is mostly about efficient string comparison. Since every candidate word must match the beginning of s, the solution focuses on checking prefix relationships without unnecessary work.
Approach 1: Simple Iteration and Comparison (O(n * m) time, O(1) space)
The most direct solution iterates through every word in the array. For each word, check whether it is a prefix of s. In most languages this is a single operation such as startsWith(), or you can manually compare characters until the word length is reached.
If the word length exceeds s, it cannot be a prefix, so skip it. Otherwise compare characters from index 0 to word.length - 1. Increment a counter whenever all characters match. The algorithm scans each word once, and the comparison takes up to the length of the word.
This results in O(n * m) time complexity where n is the number of words and m is the average word length. Space complexity stays O(1) because only a counter is maintained. For this problem's constraints, this solution is already optimal and extremely readable.
Approach 2: Using Trie Data Structure to Optimize Prefix Checking (O(n * m) build + O(m) traversal, O(n * m) space)
A more structured approach builds a Trie from the list of words. Each path in the Trie represents characters of a word, and terminal nodes mark completed words.
Once the Trie is built, traverse the target string s character by character. Each time you reach a node marked as a completed word, increment the prefix count. Stop traversal when the next character is not present in the Trie.
This approach works because every valid prefix must lie along the path defined by the characters of s. Trie traversal avoids repeatedly comparing characters across different words. The build phase costs O(n * m), and the traversal costs O(m). Space usage is O(n * m) for storing Trie nodes.
Recommended for interviews: The simple iteration solution is usually what interviewers expect first. It demonstrates clear reasoning about prefix checks and runs efficiently for typical constraints. Mentioning the Trie optimization shows deeper knowledge of prefix-based data structures and scalability for large dictionaries.
Approach 1: Simple Iteration and Comparison
This approach involves iterating through each word in the array and checking if it is a prefix of the string s. A word is considered a prefix of s if the initial portion of s with the length of the word matches the word itself. For each word, extract the substring from s equating to the length of the word and compare the two.
def countPrefixes(words, s):
return sum(s.startswith(word) for word in words)
words = ["a", "b", "c", "ab", "bc", "abc"]
s = "abc"
result = countPrefixes(words, s)
print(result) # Output: 3import java.util.*;
public class CountPrefixes {
public static int countPrefixes(String[] words, String s) {
int count = 0;
for (String word : words) {
if (s.startsWith(word)) {
count++;
}
}
return count;
}
public static void main(String[] args) {
String[] words = {"a", "b", "c", "ab", "bc", "abc"};
String s = "abc";
int result = countPrefixes(words, s);
System.out.println(result); // Output: 3
}
}#include <vector>
#include <string>
#include <iostream>
int countPrefixes(std::vector<std::string>& words, std::string s) {
int count = 0;
for (const auto& word : words) {
if (s.compare(0, word.size(), word) == 0) {
count++;
}
}
return count;
}
int main() {
std::vector<std::string> words = {"a", "b", "c", "ab", "bc", "abc"};
std::string s = "abc";
int result = countPrefixes(words, s);
std::cout << result << std::endl; // Output: 3
return 0;
}function countPrefixes(words, s) {
return words.reduce((count, word) => count + (s.startsWith(word) ? 1 : 0), 0);
}
const words = ["a", "b", "c", "ab", "bc", "abc"];
const s = "abc";
const result = countPrefixes(words, s);
console.log(result); // Output: 3#include <stdio.h>
#include <string.h>
int countPrefixes(char * words[], int wordsSize, char * s) {
int count = 0;
for (int i = 0; i < wordsSize; i++) {
if (strncmp(words[i], s, strlen(words[i])) == 0) {
count++;
}
}
return count;
}
int main() {
char *words[] = {"a", "b", "c", "ab", "bc", "abc"};
char *s = "abc";
int result = countPrefixes(words, 6, s);
printf("%d\n", result); // Output: 3
return 0;
}using System;
public class Solution {
public int CountPrefixes(string[] words, string s) {
int count = 0;
foreach (var word in words) {
if (s.StartsWith(word)) {
count++;
}
}
return count;
}
public static void Main(string[] args) {
string[] words = {"a", "b", "c", "ab", "bc", "abc"};
string s = "abc";
Solution solution = new Solution();
int result = solution.CountPrefixes(words, s);
Console.WriteLine(result); // Output: 3
}
}This Python function calculates the total number of prefixes in one line using a generator expression and the startswith() method, which checks each word against s.
Time Complexity: O(n * k), where n is the number of words, and k is the maximum length of a word.
Space Complexity: O(1), as no extra space is used apart from input storage.
Approach 2: Using Trie Data Structure to Optimize Prefix Checking
A more advanced approach employs a Trie (prefix tree) to efficiently check prefix relations. By inserting all possible prefixes of the string s into a Trie, you can then quickly check if each word is a prefix by verifying its existence in the Trie.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
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.is_end_of_word = True
def is_prefix(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return True
def count_prefixes(words, s):
trie = Trie()
for i in range(1, len(s) + 1):
trie.insert(s[:i])
count = 0
for word in words:
if trie.is_prefix(word):
count += 1
return count
words = ["a", "b", "c", "ab", "bc", "abc"]
s = "abc"
result = count_prefixes(words, s)
print(result) # Output: 3import java.util.*;
class TrieNode {
Map<Character, TrieNode> children;
boolean isEndOfWord;
public TrieNode() {
children = new HashMap<>();
isEndOfWord = false;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node = node.children.computeIfAbsent(c, k -> new TrieNode());
}
node.isEndOfWord = true;
}
public boolean isPrefix(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (!node.children.containsKey(c)) {
return false;
}
node = node.children.get(c);
}
return true;
}
}
public class CountPrefixes {
public static int countPrefixes(String[] words, String s) {
Trie trie = new Trie();
for (int i = 1; i <= s.length(); ++i) {
trie.insert(s.substring(0, i));
}
int count = 0;
for (String word : words) {
if (trie.isPrefix(word)) {
count++;
}
}
return count;
}
public static void main(String[] args) {
String[] words = {"a", "b", "c", "ab", "bc", "abc"};
String s = "abc";
int result = countPrefixes(words, s);
System.out.println(result); // Output: 3
}
}#include <vector>
#include <string>
#include <iostream>
#include <unordered_map>
class TrieNode {
public:
std::unordered_map<char, TrieNode*> children;
bool isEndOfWord;
TrieNode() : isEndOfWord(false) {}
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
void insert(const std::string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c)) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->isEndOfWord = true;
}
bool isPrefix(const std::string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c)) {
return false;
}
node = node->children[c];
}
return true;
}
};
int countPrefixes(std::vector<std::string>& words, std::string s) {
Trie trie;
for (int i = 1; i <= s.size(); ++i) {
trie.insert(s.substr(0, i));
}
int count = 0;
for (const auto& word : words) {
if (trie.isPrefix(word)) {
count++;
}
}
return count;
}
int main() {
std::vector<std::string> words = {"a", "b", "c", "ab", "bc", "abc"};
std::string s = "abc";
int result = countPrefixes(words, s);
std::cout << result << std::endl; // Output: 3
return 0;
}This Python solution uses a Trie to store all prefixes of the string s. The count_prefixes() function checks each word against this Trie to determine its prefix status.
Time Complexity: O(m + n * k), where m is the length of string s (for building the Trie), and n is the number of words (each with average length k checked against the Trie).
Space Complexity: O(m * 26), due to storage requirements for the Trie nodes.
Approach 3: Traversal Counting
We directly traverse the array words, and for each string w, we check if s starts with w as a prefix. If it does, we increment the answer by one.
After the traversal, we return the answer.
The time complexity is O(m times n), where m and n are the lengths of the array words and the string s, respectively. The space complexity is O(1).
function countPrefixes(words: string[], s: string): number {
return words.filter(w => s.startsWith(w)).length;
}func countPrefixes(words []string, s string) (ans int) {
for _, w := range words {
if strings.HasPrefix(s, w) {
ans++
}
}
return
}impl Solution {
pub fn count_prefixes(words: Vec<String>, s: String) -> i32 {
words.iter().filter(|w| s.starts_with(w.as_str())).count() as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simple Iteration and Comparison | Time Complexity: O(n * k), where n is the number of words, and k is the maximum length of a word. |
| Using Trie Data Structure to Optimize Prefix Checking | Time Complexity: O(m + n * k), where m is the length of string s (for building the Trie), and n is the number of words (each with average length k checked against the Trie). |
| Traversal Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Iteration and Prefix Comparison | O(n * m) | O(1) | Best for most cases. Easy to implement and efficient for moderate input sizes. |
| Trie-Based Prefix Matching | O(n * m) build + O(m) query | O(n * m) | Useful when checking many prefix queries against the same dictionary. |
Frequently asked questions
Is Count Prefixes of a Given String easy or hard?
Count Prefixes of a Given String is classified as an Easy problem. The logic mainly involves basic string comparison and array iteration, making it a good practice problem for beginners learning prefix operations.
How to solve Count Prefixes of a Given String in O(n)?
Pure O(n) time is not possible because prefix comparison requires checking characters of each word. The closest practical solution is O(n * m), where each word comparison stops early if characters differ. Using built-in prefix functions like startsWith keeps the implementation efficient.
Count Prefixes of a Given String Python or Java solution?
In Python, iterate through the words list and use s.startswith(word) to count matches. In Java, use s.startsWith(word) inside a loop. Both implementations run in O(n * m) time and require constant extra space.
What is the best approach for Count Prefixes of a Given String?
The best approach is simple iteration with prefix comparison. Loop through each word and check whether the target string starts with that word using startsWith or character comparison. This runs in O(n * m) time where n is the number of words and m is the word length, with O(1) extra space.
What data structure is used in Count Prefixes of a Given String?
The simplest solution only requires arrays and basic string operations. An alternative solution uses a Trie data structure to store all words and traverse the target string, which is useful when performing multiple prefix queries efficiently.
What is the time complexity of Count Prefixes of a Given String?
The typical solution runs in O(n * m) time. You check each of the n words and compare up to m characters to verify whether it matches the prefix of the target string. Space complexity is O(1) for the iterative approach.
Is Count Prefixes of a Given String asked at Google, Amazon, or Meta?
This problem represents a common string-prefix pattern that appears in interviews at companies like Amazon and Google. While the exact problem may vary, prefix checking, dictionary matching, and Trie-based string processing are frequently tested concepts.