2255. Counting Words With a Given Prefix
Problem Description
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 is any leading contiguous substring of a string.
Example:
Input: words = ["pay","attention","practice","attend"], pref = "at"
Output: 2
Explanation: The 2 strings that contain "at" as a prefix are: "attention" and "attend".
Solution Code
class Solution {
public int prefixCount(String[] words, String pref) {
int count = 0;
int prefLength = pref.length();
for (String word : words) {
if (word.length() >= prefLength && word.substring(0, prefLength).equals(pref)) {
count++;
}
}
return count;
}
}
Approach Name
Prefix Matching with Substring Comparison
Intuition
The problem requires counting how many strings in the array words
start with the given prefix pref
. We can achieve this by iterating through each word in the array and checking if the substring of the word (from the start to the length of pref
) matches pref
.
Algorithm
Initialize a Counter:
- Use a counter to keep track of the number of words that contain
pref
as a prefix.
- Use a counter to keep track of the number of words that contain
Iterate Through Words:
- For each word in the array, check if its length is at least as long as
pref
. - If it is, compare the substring of the word (from index 0 to the length of
pref
) withpref
.
- For each word in the array, check if its length is at least as long as
Count Matching Words:
- If the substring matches
pref
, increment the counter.
- If the substring matches
Return the Count:
- After iterating through all words, return the counter as the result.
Complexity Analysis
- Time Complexity: O(n * m), where
n
is the number of words in the array andm
is the length ofpref
. For each word, we perform a substring operation and a comparison, both of which take O(m) time. - Space Complexity: O(1), as we only use a constant amount of extra space for the counter and temporary variables.
Leetcode Related Problems
- Easy - 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence
- Easy - 2255. Count Prefixes of a Given String
GeeksForGeeks Related Problems
- Easy - 703505. Count number of words Related Articles: Count words in a given string