Loading page…
Practice problem · easy
A phone keeps your contacts. When you type letters in the search box, the phone shows how many contacts start with what you typed so far. That tells you when to keep typing and when to stop.
You work on that search box. You get the list of contact names and the list of typed texts, and you must answer for each typed text how many names start with it.
Write count_with_prefix(names, prefixes).
names are the contact names, in lowercase letters. The same name can appear more than once, and every copy counts.prefixes are the typed texts, one for each question.Input: names = ["anna", "ann", "bob", "anil"], prefixes = ["an", "ann", "b"]
Output: [3, 2, 1]| Typed text | Names that start with it | Count |\n|---|---|---|\n| an | anna, ann, anil | 3 |\n| ann | anna, ann | 2 |\n| b | bob | 1 |\n\nA name that equals the typed text counts as well.
Input: names = ["sam", "sam", "sara"], prefixes = ["sa", "sam", "z"]
Output: [3, 2, 0]The same name twice counts twice. No name starts with "z".
Input: names = ["lee"], prefixes = ["leeds"]
Output: [0]The typed text is longer than the name, so the name cannot start with it.
1 ≤ length of names ≤ 5000 and 1 ≤ length of prefixes ≤ 5000a to z)There can be 5,000 names and 5,000 typed texts. Checking every name for every typed text is 25 million checks, each up to 20 letters. That still passes here, but a phone with a million contacts would not.
A trie answers each typed text by walking only its own letters, however many names there are.
count_with_prefix · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.