Prefix Count
Solve an easy problem of counting prefixes of strings using tries.
Problem statement
A prefix of a string is any leading contiguous substring of the string. Given an array of strings words and a string pref, return the number of strings in words that contain pref as a prefix.
Example 1
Sample input
words: ["pay", "paid", "pat", "app", "apple", "apply", "ape"]pref: "pa"
Sample output
3
Explanation
There are three strings in the list of words that contain "pa" as a prefix, i.e. "pay", "paid"
and "pat".
Example 2
Sample Input
words: [“pay”, “paid”, “pat”, “app”, “apple”, “apply”, “ape”]pref: "ap"
Sample output
4
Explanation
There are four strings "app", "apple", "apply", and "ape" that contain "ap" as a prefix.
Try it yourself
Please try to solve the problem yourself before reading the solution.
#include <iostream>#include <vector>using namespace std;int prefixCount(vector<string>& words, string prefix) {// your code goes herereturn -1;}
Intuition
The problem can be rephrased as counting the number of words in a list with a given prefix. A naive solution would be to traverse through all the words in the given list and check if the word has pref as the prefix.
// returns the count of words in the list, which have pref as a prefixint prefixCount(words, pref){count = 0for every word in words list//check if pref is a prefix of wordif isPrefix(pref, word) is truecount+1return count}// checks if pref is a prefix of wordboolean isPrefix(pref, word){for char at index i the pref and in the wordif character at index in pref, equals to the character at index in wordcontinueelsebreakif the value of index equals the length of prefreturn true}
To check if pref is a prefix of a word, we traverse and compare all characters of both the word and pref simultaneously. This operation adds a time complexity of