Count Prefixes of a Given String
Problem
You are given a list of strings words and a string s. Return the number of strings in words that are a prefix of s. A prefix of s is a string that matches the first characters of s exactly.
words = ["a","b","c","ab","bc","abc"], s = "abc"3def count_prefixes(words, s):
count = 0
for w in words:
if s.startswith(w):
count += 1
return countfunction countPrefixes(words, s) {
let count = 0;
for (const w of words) {
if (s.startsWith(w)) {
count++;
}
}
return count;
}class Solution {
public int countPrefixes(String[] words, String s) {
int count = 0;
for (String w : words) {
if (s.startsWith(w)) {
count++;
}
}
return count;
}
}int countPrefixes(vector<string>& words, string s) {
int count = 0;
for (const string& w : words) {
if (s.rfind(w, 0) == 0) {
count++;
}
}
return count;
}Explanation
A word is a prefix of s when it lines up with the very start of s, character for character. So the whole task is just: for each word, ask "does s begin with this word?" and tally up the yeses.
We keep a running count. Walking through words one at a time, we call the language's built-in startsWith (or rfind(w, 0) == 0 in C++) which returns true exactly when w matches the leading characters of s.
Every time the check passes we increment count. Words that are longer than s, or that differ at any leading position, simply fail the test and are skipped.
There is no need for sorting or any clever data structure here — the list is small and a single linear pass with a constant-cost membership test per word is already optimal for the constraints.
Example: words = ["a","b","c","ab","bc","abc"], s = "abc". The words "a", "ab" and "abc" all begin "abc"; "b", "c" and "bc" do not. So the answer is 3.