Counting Words With a Given Prefix

Easy
1754.

Counting Words With a Given Prefix

Counting Words With a Given Prefix is an easy coding problem on arrays, strings and string matching, asked in Amazon and Google interviews.

You are given an array of strings words and a string pref.

Return the number of strings in words that have pref as a prefix — that is, that begin with pref. A string is a prefix of itself.

Example 1

Input
words = ["kairo","kai","code","kaizen"], pref = "kai"
Output
3
Explanation
`"kairo"`, `"kai"` and `"kaizen"` start with `"kai"`.

Example 2

Input
words = ["leetcode","win","loops","success"], pref = "code"
Output
0
Explanation
`"code"` appears inside `"leetcode"` but not at its start.

Example 3

Input
words = ["abc"], pref = "abcd"
Output
0
Explanation
A prefix cannot be longer than the word.

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length, pref.length <= 100
  • words[i] and pref consist of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @param {string} pref
 * @return {number}
 */
var prefixCount = function(words, pref) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Counting Words With a Given Prefix — Problem & Solution

Counting Words With a Given Prefix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Counting Words With a Given Prefix is an easy coding problem on arrays, strings and string matching, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Strings, String Matching
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array of strings words and a string pref.

Return the number of strings in words that have pref as a prefix — that is, that begin with pref. A string is a prefix of itself.

Example 1

Input: words = ["kairo","kai","code","kaizen"], pref = "kai"
Output: 3
Explanation: `"kairo"`, `"kai"` and `"kaizen"` start with `"kai"`.

Example 2

Input: words = ["leetcode","win","loops","success"], pref = "code"
Output: 0
Explanation: `"code"` appears inside `"leetcode"` but not at its start.

Example 3

Input: words = ["abc"], pref = "abcd"
Output: 0
Explanation: A prefix cannot be longer than the word.

Constraints

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

Hints for Counting Words With a Given Prefix

  1. Hint 1

    Each word can be checked on its own.

  2. Hint 2

    A word has the prefix when it is at least as long as pref and its first |pref| characters equal pref.

  3. Hint 3

    Most languages have a built-in startsWith for exactly this.

How to solve Counting Words With a Given Prefix

Test every word with a prefix comparison and count the matches.

Approach

  1. Set count = 0.
  2. For each word, if it starts with pref, increment count.
  3. Return count.

Complexity

  • Time — O(n · |pref|)
  • Space — O(1)

Pitfalls

  • A substring match anywhere in the word is not enough — it must be at the start.
  • Guard the length when comparing manually: a word shorter than pref never matches.

Reference solution

Python

from typing import List

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

Java

public static int prefixCount(String[] words, String pref) {
    int count = 0;
    for (String w : words) if (w.startsWith(pref)) count++;
    return count;
}

C++

int prefixCount(vector<string>& words, string pref) {
    int count = 0;
    for (const string& w : words) {
        if (w.size() >= pref.size() && w.compare(0, pref.size(), pref) == 0) count++;
    }
    return count;
}

JavaScript

var prefixCount = function(words, pref) {
    var count = 0;
    for (var i = 0; i < words.length; i++) {
        if (words[i].substring(0, pref.length) === pref) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings