#232EasyTries· Prefix Counters

Autocomplete Prefix Count

A search box shows how many saved queries start with the text typed so far. The product team wants the counter to stay instant while millions of queries are stored, so scanning the whole list on every keystroke is not acceptable. Design a class `PrefixCounter`: - `PrefixCounter()` creates an empty counter. - `addWord(word)` stores one more query. Saving the same word twice counts it twice. - `countWithPrefix(prefix)` returns how many stored queries start with `prefix`. A query counts as starting with itself.

Input format

`operations`: the method names in call order (the first is the constructor); `arguments`: the argument list of each call.

Output format

One value per operation: `null` for the constructor and `addWord`, and the count for each `countWithPrefix`.

Examples

Input: operations = ["PrefixCounter", "addWord", "addWord", "addWord", "countWithPrefix", "countWithPrefix", "countWithPrefix"], arguments = [[], ["apple"], ["app"], ["apple"], ["app"], ["apple"], ["b"]]

Output: [null, null, null, null, 3, 2, 0]

Three queries are stored: apple, app and apple again. The prefix app matches all three. The prefix apple matches the two copies of apple. Nothing starts with b.

Input: operations = ["PrefixCounter", "countWithPrefix", "addWord", "countWithPrefix", "countWithPrefix"], arguments = [[], ["a"], ["a"], ["a"], ["ab"]]

Output: [null, 0, null, 1, 0]

An empty counter returns 0. After storing a, the prefix a matches it once, while ab matches nothing because the stored word is shorter than the prefix.

Constraints

1 <= word.length, prefix.length <= 50
`word` and `prefix` use lowercase English letters only.
At most 10^5 calls in total.

Study first

Tries (Prefix Trees)

#trie
#design
#strings
#prefix