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

1. Initialize a Counter:

   • Use a counter to keep track of the number of words that contain pref as a prefix.

2. 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) with pref.

3. Count Matching Words:

   • If the substring matches pref, increment the counter.

4. 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 and m is the length of pref. 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

1. Easy - 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence
2. Easy - 2255. Count Prefixes of a Given String

GeeksForGeeks Related Problems

1. Easy - 703505. Count number of words Related Articles: Count words in a given string