Trie Data Structure Implementation

EasyPython

Problem

Quantcast may need to index keyword and prefix signals efficiently. Implement a trie with insert, search, and startsWith operations.

Create a Trie class with these methods:

insert(word): Add a lowercase word to the trie.
search(word): Return True only when the complete word has been inserted.
startsWith(prefix): Return True when at least one inserted word begins with prefix.

For automated evaluation, implement process_trie_operations(operations). Each operation is a dictionary with op equal to insert, search, or startsWith, and a word field. The function must return results only for search and startsWith operations, in their original order.

Formal Specification

Input: A list of operation dictionaries, where each dictionary has op: str and word: str.
Output: A list of booleans produced by search and startsWith operations.
Words contain only lowercase English letters and are nonempty.

Constraints

1 <= len(operations) <= 10^4
1 <= len(word) <= 100
Words contain only lowercase English letters
At most 5 * 10^3 distinct words are inserted
Operations are processed in order

Function Signature

def process_trie_operations(operations):

Quantcast may need to index keyword and prefix signals efficiently. Implement a trie with insert, search, and startsWith operations.

Create a Trie class with these methods:

insert(word): Add a lowercase word to the trie.
search(word): Return True only when the complete word has been inserted.
startsWith(prefix): Return True when at least one inserted word begins with prefix.

Formal Specification

Input: A list of operation dictionaries, where each dictionary has op: str and word: str.
Output: A list of booleans produced by search and startsWith operations.
Words contain only lowercase English letters and are nonempty.