Prefix Tree Supporting Insert, Exact Search and Prefix Queries

Build a word index over lowercase English words that supports three operations, applied in the order given:

• ["insert", w]: add the word w to the index
• ["search", w]: report whether the word w itself has been inserted
• ["prefix", p]: report whether at least one inserted word starts with p

Process a list of such operations and return the answers to the search and prefix operations, in the order those operations appear.

Function Signature

def run_word_index(operations: List[List[str]]) -> List[bool]:

Rules

• The index starts empty.
• Each operation is a two-element list: the operation name, then a word or prefix.
• insert produces no answer. Inserting a word that is already present changes nothing.
• search is true only for an exact match of a previously inserted word; being a prefix of an inserted word is not enough.
• prefix is true when some inserted word starts with p, including a word equal to p.
• Each operation sees only the words inserted before it.
• Return an empty list when there are no search or prefix operations.

Constraints

• 1 <= len(operations) <= 2 * 10^4
• Every operation name is one of "insert", "search", "prefix"
• Every word and prefix has length between 1 and 100 and contains only the lowercase letters a to z

Examples

Example 1

operations = [["insert", "card"], ["search", "car"], ["prefix", "car"],
 ["insert", "car"], ["search", "car"], ["search", "cards"]]
output = [False, True, True, False]

Before "car" is inserted it is only a prefix of "card", so the exact search fails while the prefix check succeeds. After the second insert the exact search succeeds, and "cards" was never inserted.

Example 2

operations = [["prefix", "a"], ["insert", "a"], ["prefix", "a"],
 ["search", "a"], ["search", "ab"]]
output = [False, True, True, False]

Example 3

operations = [["insert", "x"]]
output = []