Count Words by Prefix
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Given a dictionary words and a list of inputs queries, return for each queries[j] the number of words that start
with queries[j], in query order. A word counts as starting with itself, and duplicate words are counted separately.
Examples
| words | queries | result |
|---|---|---|
["apple", "app", "apply", "bat", "bath"] | ["app", "ba", "c", "apple"] | [3, 2, 0, 1] |
["a", "a", "ab"] | ["a", "ab", "abc"] | [3, 1, 0] |
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(words: string[], queries: string[]) → int[]
Constraints
-
words.length,queries.length - Every word and query is non-empty and consists of lowercase English letters.
- Total length of
words, total length ofqueries
Expected complexity
- Time
- O(sum of lengths)
- Space
- O(sum of word lengths)
Examples
| words | queries | Expected |
|---|---|---|
["apple","app","apply","bat","bath"] | ["app","ba","c","apple"] | [3,2,0,1] |
["a","a","ab"] | ["a","ab","abc"] | [3,1,0] |
Hint
Hint
Insert every word into a trie, incrementing a counter on each node passed; a node's counter is the number of words with
that prefix, so a query walks down its letters and reads the counter (0 if the path breaks). Alternatively, sort the
words: those starting with q form one contiguous block found by two binary searches. Scanning all words per query is
and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1506 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 2 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |