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 ```python 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 = [] ```