Autocomplete Word Store

medium

You're building the word store behind a search box's autocomplete. It must ingest words, answer "is this exact word stored?", and — the part hash sets can't do — answer "does anything stored begin with these letters?" the instant a user pauses typing.

Operations format. Your function receives one argument ops: a list of operations, each itself a list — ["insert", word], ["search", word], or ["starts_with", prefix]. Process them in order and return a list with one entry per operation: None for insert, and True/False for search (exact word stored?) and starts_with (any stored word begins with this prefix?). All strings are lowercase letters.

Example 1

in ops = [["insert", "apple"], ["search", "apple"], ["search", "app"], ["starts_with", "app"], ["insert", "app"], ["search", "app"]]

out [None, True, False, True, None, True]

"app" is a prefix of a stored word but not a stored word itself — until it gets inserted.

Example 2

in ops = [["search", "ghost"]]

out [False]

Nothing stored yet.

Constraints

· 1 <= len(ops) <= 2000
· 1 <= len(word) <= 200
· words and prefixes are lowercase English letters