Implement Trie (Prefix Tree)

Medium· trie· design

Problem

Build a trie with three operations: insert(word) adds a word, search(word) reports whether that exact word was inserted, and startsWith(prefix) reports whether any inserted word begins with the prefix.

Examples

Input: insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")

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

"app" is only a prefix until it is inserted as a word in its own right.

Constraints

• 1 <= word.length, prefix.length <= 2000
• Lowercase English letters only
• Up to 3 * 10^4 calls in total

Hints & approach

Hint 1

Each node represents a prefix and has up to 26 children, one per next letter.

Hint 2

A node also needs a flag saying whether a whole word ends there.

Hint 3

search and startsWith walk the same path; they differ only in what they check at the end.

Approachtry the hints first

Each node holds a children map (or 26-slot array) and an isEnd flag. insert walks from the root, creating missing child nodes letter by letter, and sets isEnd on the last node. A shared helper walks a string and returns the node it ends on, or null if a letter is missing. search returns true only if that node exists and has isEnd set; startsWith only needs the node to exist.

Time O(L) per operation · Space O(total inserted characters)

Next →Replace Words