2185. Counting Words With a Given Prefix
Problem Description
The task is to count how many strings from the given array words
have the string pref
as their prefix. A prefix is defined as a substring that appears at the start of another string. For example, if pref
is "ab", and you have a string "abcd" in words
, it counts because "abcd" starts with "ab".
Intuition
The intuitive solution to this problem is straightforward. You simply iterate through each string in the array words
and check if it starts with the string pref
. The method startswith()
in Python is perfect for this task as it does exactly what's neededāit returns True
if the string object it's called on starts with the specified prefix, which in this case, is pref
.
By using a list comprehension, we effectively generate a list of boolean values, True
for strings that start with pref
and False
otherwise. Wrapping this list comprehension with Python's sum()
function cleverly counts the number of True
values in that list, because True
is equivalent to 1
and False
is equivalent to 0
when it comes to addition. Hence, we get the total count of strings with the given prefix in one elegant line of code.
Solution Approach
The solution is implemented in Python and makes use of a list comprehension and the built-in startswith()
method for strings. The elegance of the solution lies in its simplicity and efficient use of the language's features.
Here are the steps taken in the algorithm:
-
Loop through each string
w
in the arraywords
using a list comprehension. For each string, check if it starts with the prefixpref
. This is done using thestartswith()
method, which is called on eachw
. -
The
startswith()
method returns a boolean valueTrue
orFalse
. This list comprehension creates a list of boolean values corresponding to each string inwords
. -
The
sum()
function is then used to add up all the boolean values in the list. In Python,True
is treated as1
andFalse
as0
when summed. So,sum()
essentially counts all theTrue
values, which represent the strings that start withpref
. -
The result of the
sum()
function gives us the total number of strings inwords
that containpref
as a prefix.
The code for this solution is concise and can be written as:
class Solution:
def prefixCount(self, words: List[str], pref: str) -> int:
return sum(w.startswith(pref) for w in words)
This code fragment is the complete implementation of the solution. It defines a class Solution
with a method prefixCount
, which takes an array of strings words
and a string pref
as arguments and returns an integer. The prefixCount
method only contains the above-mentioned list comprehension wrapped in the sum()
function, which calculates and returns the count directly.
The solution does not require additional data structures and is a good example of Python's expressive capability to solve problems in a very readable and succinct manner.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution with a small example. Suppose we have an array of strings words
that contains ["apple", "appreciate", "appetite", "banana", "application"]
and our prefix pref
is "app"
.
As we iterate through words
:
- The first word
"apple"
starts with"app"
.startswith()
returnsTrue
. - The second word
"appreciate"
also starts with"app"
.startswith()
returnsTrue
. - The third word
"appetite"
starts with"app"
as well.startswith()
returnsTrue
. - The fourth word
"banana"
does not start with"app"
.startswith()
returnsFalse
. - The fifth word
"application"
starts with"app"
.startswith()
returnsTrue
.
Using the list comprehension [w.startswith(pref) for w in words]
, we get a list of boolean values:
[True, True, True, False, True]
.
Passing this list to the sum()
function adds up the True
values (with each True
being equivalent to 1
):
sum([True, True, True, False, True])
which equals 1 + 1 + 1 + 0 + 1
, giving us a total of 4
.
So, the total count of strings with the prefix "app"
in the words
array is 4
. This demonstrates the simplicity and elegance of the solution using Python's built-in functions.
Solution Implementation
1from typing import List # Import List from typing module for type annotation
2
3class Solution:
4 def prefix_count(self, words: List[str], pref: str) -> int:
5 # Count the number of words that start with the given prefix
6 # Args:
7 # words: A list of strings representing the words
8 # pref: A string representing the prefix to be matched
9 # Returns:
10 # The count of words starting with the given prefix
11
12 # Use a generator expression to iterate over 'words' list
13 # The 'startswith()' method is used to check if the word starts with 'pref'
14 # 'sum()' function adds up how many times True appears (i.e., where the condition is met)
15 return sum(word.startswith(pref) for word in words)
16
1class Solution {
2 // Method to count how many strings in the words array have the prefix 'pref'
3 public int prefixCount(String[] words, String pref) {
4 int count = 0; // Initialize counter to track number of words with the prefix
5 // Iterate through each word in the array
6 for (String word : words) {
7 // Check if the current word starts with the given prefix
8 if (word.startsWith(pref)) {
9 // Increment the count if the word has the prefix
10 count++;
11 }
12 }
13 // Return the total count of words with the prefix
14 return count;
15 }
16}
17
1#include <vector>
2#include <string>
3
4class Solution {
5public:
6 // Function to count the number of words in 'words' that start with the given prefix 'pref'
7 int prefixCount(vector<string>& words, const string& pref) {
8 int count = 0; // Initialize a variable to store the count of words with the given prefix
9 for (const auto& word : words) { // Iterate over each word in the vector 'words'
10 if (word.find(pref) == 0) { // Check if 'pref' is a prefix of 'word'
11 count++; // Increment the count if the word starts with the given prefix
12 }
13 }
14 return count; // Return the total count of words with the given prefix
15 }
16};
17
1// Counts the number of words in the array that start with the given prefix.
2// @param words - An array of strings to be checked against the prefix.
3// @param prefix - The prefix string to match at the beginning of each word.
4// @returns The count of words starting with the specified prefix.
5function prefixCount(words: string[], prefix: string): number {
6 // Use Array.prototype.reduce to accumulate the count of words starting with the prefix.
7 // - The callback function checks if the current word starts with the prefix.
8 // - If it does, increment the accumulator.
9 // - The initial value of the accumulator is set to 0.
10 return words.reduce((accumulator, currentWord) => (
11 accumulator += currentWord.startsWith(prefix) ? 1 : 0
12 ), 0);
13}
14
Time and Space Complexity
The given Python function prefixCount
iterates over each word in the list words
and checks if it starts with the prefix pref
using the startswith
method. The computation complexity analysis is as follows:
Time Complexity
The time complexity of the function is O(n * k)
, where n
is the number of words in the list and k
is the length of the prefix pref
. This is because for each of the n
words, the startswith
method checks up to k
characters to determine if the word starts with the prefix.
Space Complexity
The space complexity of the function is O(1)
. The function uses a generator expression within the sum
function, which calculates the result on-the-fly and does not require additional space proportional to the input size. The only additional memory used is for the counter in the sum
function, which is a constant space requirement.
Learn more about how to find time and space complexity quickly using problem constraints.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!