Implement Trie (Prefix Tree)

MediumtrieGoogleAmazonMicrosoftMetaTwitter

A **trie** (pronounced as "try") or **prefix tree** is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

- Trie() Initializes the trie object.

- void insert(String word) Inserts the string word into the trie.

- boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.

- boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Examples

Input:

commands = ["Trie", "insert", "search", "search", "startsWith", "insert", "search"], args = [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output:[null, null, true, false, true, null, true]

Explanation:Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True

Constraints

1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.

💡 Hints

Hint 1

Each node has a map of child nodes by character and a boolean flag indicating if it ends a complete word.

Hint 2

For startsWith, traverse the prefix. If every character is present, return true even if isEndOfWord is false.

Hint 3

For search, traverse the word and ensure the final node has isEndOfWord set to true.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Linear

Algorithmic Approach

Store characters in a tree hierarchy where each edge represents a letter. Maintain an isEnd flag to distinguish complete words from prefixes.

Time ComplexityO(L) per operation

Why:

Insert, search, and startsWith operations traverse exactly L characters of the input string in O(1) per character.

Space ComplexityO(N * L)

Why:

Up to N keys each of length L can generate TrieNodes with up to 26 child references each.

Big-O Growth CurveLinear (O(N))

Execution time scales directly in proportion to the input size.

🌍 Real-World Use Cases

ChromeURL Omnibox History & Suggestions

Fast keystroke-by-keystroke prefix lookups using an in-memory Trie data structure.

🔍 Dry Run

Solution⏱ O(L) per operation | 💾 O(N * L)

•

Line1

root=TrieNode(root)Trie

Initialize Trie root with empty children map.