Implement Trie Prefix Tree

Medium · Tries

Design a data structure that stores a set of lowercase words and supports three operations. Insert adds a word to the structure. Search reports whether an exact word was previously inserted. StartsWith reports whether any inserted word begins with a given prefix, even if that prefix itself was never inserted as a whole word. Build this so all three operations work efficiently even after many calls.

Examples

Input:  insert("apple"), search("apple") -> True, search("app") -> False, startsWith("app") -> True, insert("app"), search("app") -> True
Output: True, False, True, True
Why:    After inserting apple, only the exact word apple is stored, so search(app) fails but startsWith(app) succeeds; inserting app then makes search(app) succeed too.

Input:  insert("cat"), insert("car"), search("ca") -> False, startsWith("ca") -> True, search("cat") -> True
Output: False, True, True
Why:    ca is only a prefix shared by cat and car, never inserted as a full word, while cat was explicitly inserted.

Input:  insert("a"), search("a") -> True, startsWith("") -> True
Output: True, True
Why:    A single letter word is stored fully, and the empty prefix matches everything in a non-empty trie.

Constraints

1 <= word.length, prefix.length <= 2000, words and prefixes consist only of lowercase English letters, the total number of calls to insert, search and startsWith is at most 3 * 10^4

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Implement Trie Prefix Tree

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Implement Trie Prefix Tree. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.