You are 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 of a string s is any leading contiguous substring of s.

Examples

Example 1:

Input: words = ["pay","attention","practice","attend"], pref = "at"
Output: 2
Explanation: 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
Explanation: 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.

Thinking Process

  1. Simple Prefix Matching: Use substring comparison for clarity
  • Strings often need frequency maps or two-pointer scans.
  • Watch index bounds and empty-string edge cases.
  • Stack helps with nested or repeated patterns.
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Two pointers on string (this problem) O(n) O(1) Palindrome, parsing
Hash map / frequency O(n) O(k) Anagram, character counts
KMP / rolling hash O(n) O(n) Pattern matching
Stack parsing O(n) O(n) Decode string, parentheses

Solution

class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        int cnt = 0;
        const int prel = pref.length();
        for(auto& word: words) {
            if(word.substr(0, prel) == pref) {
                cnt++;
            }
        }
        return cnt;
    }
};

Solution Explanation

Approach: Two pointers on string (this problem)

Key idea: 1. Simple Prefix Matching: Use substring comparison for clarity

How the code works:

  1. Simple Prefix Matching: Use substring comparison for clarity
    • Strings often need frequency maps or two-pointer scans.
    • Watch index bounds and empty-string edge cases.
    • Stack helps with nested or repeated patterns.

Walkthrough — input words = ["pay","attention","practice","attend"], pref = "at", expected output 2:

The 2 strings that contain “at” as a prefix are: “attention” and “attend”.

Common Mistakes

  1. Word shorter than prefix: substr(0, prel) returns a shorter string, comparison fails correctly
  2. Empty prefix: If pref = "", all words match (but constraints guarantee pref.length >= 1)
  3. Prefix equals word: Word still counts (e.g., pref = "at", word = "at" → match)
  4. No matches: Returns 0 correctly
  5. All words match: Returns words.length

  6. Single character prefix: Works correctly with pref = "a"

  7. Out-of-bounds access: Not checking word length before accessing characters
  8. Off-by-one errors: Incorrect substring indices
  9. Case sensitivity: Problem states lowercase only, but worth noting
  10. Forgetting to increment counter: Missing the increment statement
  11. Using wrong comparison: Comparing entire word instead of prefix

When to Use This Pattern

  1. Prefix Matching: Checking if strings start with specific patterns
  2. Filtering: Selecting items from a collection based on prefix
  3. Autocomplete: Finding words that start with user input
  4. String Processing: Text analysis and pattern matching
  5. Data Validation: Checking format or structure of strings

Key Takeaways

  1. Simple Prefix Matching: Use substring comparison for clarity
  2. Length Safety: substr(0, prel) automatically handles cases where word is shorter than prefix (returns shorter substring)
  3. Efficient: Linear time complexity, suitable for given constraints
  4. Readable: Clear and straightforward implementation

References

Template Reference