Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Implement a Trie

Triesmedium

Course · Section 9: Data Structures, Modern Operators and Strings · Lecture 124: Maps: Fundamentals

Implement a prefix tree (trie). Implement `Trie`: - `insert(word)` adds a word. - `search(word)` returns whether the exact word was inserted. - `startsWith(prefix)` returns whether any inserted word starts with prefix.

Examples

Input: insert('apple'), search('apple'), search('app'), startsWith('app'), insert('app'), search('app')
Output: [true, false, true, true]
'app' is only a prefix until it is inserted, after which search('app') is true.

Sample tests

Input: insert and query
Output: [true,false,true,true]
Input: missing prefix
Output: [false,false]

+ 1 hidden test run on Submit.

Hints

Common pitfalls
  • Treating a prefix as a complete word (forgetting the end flag in search).

Learning resources

  • Wikipedia: Trie
Approach & explanation (try first)

A trie stores words character by character; the end flag distinguishes a full word from a prefix. Each operation is O(word length).

Loading...
⌘/Ctrl + Enter

Run your code to see results.