Prefix Matcher

DatadogMedium

Implement the class PrefixMatcher. add(prefix) stores a prefix, and match(strings) reports which of the given strings begin with at least one stored prefix.

Part 1: Match strings against stored prefixes

Implement the class PrefixMatcher:

add(prefix) stores prefix. Adding the same prefix again changes nothing.
match(strings) returns the strings from strings that begin with at least one stored prefix, keeping the order of strings. A string identical to a stored prefix matches. A string that begins with several stored prefixes appears once in the result. If the same string occurs twice in strings and matches, it appears twice. An empty string never matches, since every stored prefix is non-empty.

match only reads the prefixes stored so far; prefixes added later never affect an earlier call.

The matcher can hold many prefixes and match can be called many times. A call to match must not compare every string against every stored prefix: its work must stay proportional to the total length of the strings in the call plus the prefixes stored so far.

Example 1
init
[]
operations
[["add",["ab"]],["add",["xyz"]],["match",[["abc","xy","xyzzy","ba","ab"]]]]
Output
[null,null,["abc","xyzzy","ab"]]
Why: abc and ab begin with ab, and xyzzy begins with xyz. xy is shorter than xyz, so it does not match, and ba does not begin with ab.

Constraints

1 <= len(prefix)
'a' <= prefix[i] <= 'z'
strings[i] consists only of lowercase English letters and may be empty
0 <= len(strings)
The total length of all prefixes and all strings across all calls is at most 100000

Practice this question

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question