Store Words and Check Prefixes

# Store Words and Check Prefixes Implement a `Trie` object that stores lowercase words and supports exact-word and prefix queries. An exact-word query succeeds only for a word previously inserted; a prefix query can succeed even when the prefix itself has not been inserted as a word. ### Interface - `Trie()` creates an empty object. - `void insert(string word)` adds `word`. - `bool search(string word)` returns whether that complete word has been inserted. - `bool startsWith(string prefix)` returns whether any inserted word begins with `prefix`. Operations act on the same object in their given order. ### Example 1 | Operation | Result | |---|---| | `Trie()` | `null` | | `insert("stone")` | `null` | | `search("sto")` | `false` | | `startsWith("sto")` | `true` | | `insert("sto")` | `null` | | `search("sto")` | `true` | | `search("stone")` | `true` | | `search("tone")` | `false` | `null` denotes construction or a void operation. ### Example 2 A new object initially returns `false` for both `search("a")` and `startsWith("a")`. After `insert("a")`, `startsWith("a")` is `true`, while `search("aa")` remains `false`. Inserting `"a"` again does not change these membership answers. ### Constraints - `1 <= word.length, prefix.length <= 2000`. - Words and prefixes contain only lowercase English letters. - At most `30000` calls to `insert`, `search`, and `startsWith` occur in total. ### Clarifications A query does not add a word. A word can be a prefix of another stored word. Separate objects have separate contents, and duplicate insertion does not create a new kind of membership result. ### What a Strong Answer Covers - The distinction between matching a complete inserted word and matching only its beginning. - Queries before the first insertion and after duplicate insertions. - The behavior when a stored word is a prefix of a newly inserted word, and conversely. - Operation costs in terms of argument length and storage in terms of inserted text.