#2185

Easy

LeetCode Problem Workspace

Counting Words With a Given Prefix

Count how many words in a list start with a given prefix.

Problem Statement

You are given an array of strings called words and a string pref. Your task is to return the number of words in words that contain pref as a prefix.

A prefix is defined as any leading substring of a string. In other words, you must check whether each word starts with the string pref and count how many do.

Examples

Example 1

Input: words = ["pay","attention","practice","attend"], pref = "at"

Output: 2

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

There are no strings that contain "code" as a prefix.

Constraints

1 <= words.length <= 100
1 <= words[i].length, pref.length <= 100
words[i] and pref consist of lowercase English letters.

Solution Approach

Iterate Over Words

The first approach is a direct check of each word in the array. For each word, check if it starts with the prefix using the string method startsWith().

Efficient String Matching

In cases where performance is crucial, a more efficient method involves manually comparing the prefix of each word, potentially leveraging early exits to reduce unnecessary comparisons.

Edge Case Considerations

Consider edge cases where the prefix may be an empty string, or where no word in the array matches the prefix. These cases require additional checks to handle properly.

Complexity Analysis

Metric	Value
Time	O(n \cdot l + m)
Space	O(n \cdot l)

The time complexity of the solution is O(n * l), where n is the number of words and l is the average length of the words. The space complexity is O(n * l), due to the input array and prefix string comparisons.

What Interviewers Usually Probe

Check if the candidate can efficiently iterate over a list and perform string matching.
Assess if the candidate considers edge cases like empty strings or no matches.
Evaluate whether the candidate optimizes string matching appropriately for large inputs.

Common Pitfalls or Variants

Common pitfalls

Failing to handle the case where the prefix is longer than the word.
Not considering the empty string as a valid prefix.
Inefficiently checking each character of the string when more efficient methods like startsWith() exist.

Follow-up variants

What if the prefix is empty?
What if words contain varying lengths?
Can the solution be optimized for larger arrays of words?

FAQ

What is the problem title about?

The problem is about counting how many words in a list start with a given prefix.

What is the key pattern to solve this problem?

The key pattern is array iteration combined with string matching, specifically checking prefixes of words.

How can I optimize the solution for large inputs?

Consider using efficient string matching techniques and minimize unnecessary comparisons, possibly using startsWith() method.

What are some common mistakes in solving this problem?

Some common mistakes include not handling edge cases, like empty prefixes or words, or performing inefficient string comparisons.

How does GhostInterview help in solving this problem?

GhostInterview provides efficient solution suggestions and helps you identify performance bottlenecks or edge case handling issues.

terminal

Solution

Solution 1

#### Python3

1

2

3

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        return sum(w.startswith(pref) for w in words)

Solution 2

#### Python3

1

2

3

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        return sum(w.startswith(pref) for w in words)

Continue Practicing

#2301 match substring after replacement #1408 string matching in an array #3042 count prefix and suffix pairs i