Counting Words With a Given Prefix - Practice Coding Problems

Counting Words With a Given Prefix - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: Only "attention" and "attend" start with "at", so return 2

Example 2 — No Matches

$ Input: words = ["leetcode","win","loops","success"], pref = "code"

› Output: 0

💡 Note: None of the words start with "code" as a prefix

Example 3 — All Match

$ Input: words = ["car","care","careful"], pref = "car"

› Output: 3

💡 Note: All three words start with "car"

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words and target prefix

Process

Check each word if it starts with prefix

Output

Count of matching words

Key Takeaway

🎯 Key Insight: Use built-in string methods to efficiently check prefix matching for each word

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use built-in string methods like startsWith() to efficiently check if each word begins with the given prefix. Best approach uses built-in string prefix checking with Time: O(n × m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Character-by-Character Comparison	O(n × m)	O(1)	Manually compare each character of the prefix with each word
Built-in String Prefix Check	O(n × m)	O(1)	Use built-in string methods to check if word starts with prefix

Character-by-Character Comparison — Algorithm Steps

Iterate through each word in the array
For each word, compare characters with prefix manually
If all prefix characters match at start, increment counter

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Each Word

Iterate through words array

Compare Characters

Match each character of prefix with word start

Count Matches

Increment counter for complete matches

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char words[][100], int wordCount, char* pref) {
    int count = 0;
    int prefLen = strlen(pref);
    
    for (int i = 0; i < wordCount; i++) {
        if (strlen(words[i]) >= prefLen) {
            int match = 1;
            for (int j = 0; j < prefLen; j++) {
                if (words[i][j] != pref[j]) {
                    match = 0;
                    break;
                }
            }
            if (match) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON parsing for array
    char words[100][100];
    int wordCount = 0;
    char* token = strtok(line, "[],\"");
    while (token != NULL && wordCount < 100) {
        if (strlen(token) > 0 && strcmp(token, " ") != 0) {
            strcpy(words[wordCount], token);
            wordCount++;
        }
        token = strtok(NULL, "[],\"");
    }
    
    char pref[100];
    fgets(pref, sizeof(pref), stdin);
    pref[strcspn(pref, "\n")] = 0;
    
    int result = solution(words, wordCount, pref);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

n words × m average prefix length for character comparisons

✓ Linear Growth

Space Complexity

O(1)

Only using counter variable, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~8 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Character-by-Character Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler