Funcia
Lv.3binary-searchstringtrie

Count Words by Prefix

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

wordsqueriesresult
["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

  • 1≤N=1 \le N = words.length ≤100,000\le 100{,}000, 1≤Q=1 \le Q = queries.length ≤100,000\le 100{,}000
  • Every word and query is non-empty and consists of lowercase English letters.
  • Total length of words ≤106\le 10^6, total length of queries ≤106\le 10^6

Expected complexity

Time
O(sum of lengths)
Space
O(sum of word lengths)

Examples

wordsqueriesExpected
["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 O(N⋅Q)O(N \cdot Q) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251506 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample02inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.