This problem asks to count how many words from a given list begin with a specified prefix. A solution involves checking each word to see if the prefix matches its beginning, which requires efficient string matching within an array. The time complexity of an optimal solution is linear in terms of the number of words and their length, with an additional small overhead for comparing the 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?
How GhostInterview Helps
- GhostInterview can guide you through optimizing the solution for larger inputs.
- It suggests different strategies for string matching to save time and space.
- GhostInterview helps you prepare for edge cases, ensuring you handle them in an efficient manner.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Counting Words With a Given Prefix instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Counting Words With a Given Prefix from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Determine if a target substring can appear in a string after optional character replacements using given mappings efficiently.
Open problem page#1408 String Matching in an ArrayIdentify all strings in an array that appear as substrings of other strings, focusing on array and string matching patterns.
Open problem page#3042 Count Prefix and Suffix Pairs ICount all index pairs where one word is both a prefix and suffix of another, using efficient array and string checks.
Open problem page