Difficulty: MediumTries

Implement Trie (Prefix Tree)

Problem in Plain English

Implement a prefix tree that inserts lowercase words, reports whether a full word was inserted, and reports whether any inserted word starts with a given prefix. Each operation should cost time proportional to the word length, not the number of stored words.

Problem Statement

A trie, pronounced try and also called a prefix tree, is a tree data structure that stores strings so that words sharing a prefix share nodes on one path.

Implement the Trie class with void insert(word), which stores word; boolean search(word), which returns true only if word was inserted as a complete word; and boolean startsWith(prefix), which returns true if any inserted word begins with prefix.

Constraints

Word and prefix lengths satisfy $1 \leq m \leq 2000$ .
word and prefix consist only of lowercase English letters.
There are at most $3 \times 10^4$ total insert, search and prefix queries.

Examples

Example 1

Input: ["Trie","insert","search","search","startsWith","insert","search"] [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
Output: [null,null,true,false,true,null,true]

After inserting apple, app is only a prefix until it is inserted itself, at which point searching for app returns true.

Example 2

Input: ["Trie","search","startsWith","insert","insert","search","search"] [[],["a"],["a"],["a"],["a"],["a"],["aa"]]
Output: [null,false,false,null,null,true,false]

Both queries on an empty structure fail. Duplicate insertion of a is harmless; a exists exactly once as a word, while the longer aa still has no path.

Example 3

Input: ["Trie","insert","insert","search","startsWith","search","startsWith"] [[],["app"],["apple"],["app"],["appl"],["appl"],["apricot"]]
Output: [null,null,null,true,true,false,false]

Inserting apple reuses the app path without clearing its word-end flag. appl is a prefix only; apricot fails at the missing r branch even though ap is shared.

Intuition

A path spells a prefix, while a separate word-end flag says whether that prefix was inserted as a whole word. After inserting apple, the path for app exists but its last node is not terminal. Inserting app only marks that existing node; it must leave the longer apple path intact. A set can model the same semantics, but must scan stored words to answer prefix queries.

Approaches

Hash Set Scan

Solution Details

Reveal Hash Set Scan: intuition, complexity, and code

Intuition

A hash set directly checks whether a full word was inserted, while a prefix query scans stored words for a match. This keeps storage simple for small collections or workloads dominated by exact lookup, but prefix queries repeatedly compare the same shared letters.

Step-by-Step Logic

Initialize an empty set for the constructor in Example 1; insert adds the complete string, without adding its prefixes. Insert apple to get {apple}.
Answer each exact search by set membership: apple is present, while app is absent.
For a prefix query, compare the prefix with each stored word until one matches or the set is exhausted. apple begins with app, so the query succeeds.
Insert app; the set now contains both full strings, and the final exact app search succeeds. Return the Example 1 sequence [null,null,true,false,true,null,true].

Why It Works

The set contains exactly the distinct words passed to insert: adding a duplicate does not change membership. Therefore exact membership answers search. A prefix query returns true only when some member begins with the requested prefix, and examines every member before returning false, so it cannot miss a qualifying word. This is suitable for a small collection or mostly exact lookups; repeated prefix queries expose the scan cost.

Dry Run

Hash Set Scan: variable states at each step
Operation	Stored full words before → after	Check	Result
constructor	absent → {}	no inserted words	null
insert apple	{} → {apple}	add entire string	null
search apple	{apple} → {apple}	exact member found	true
search app	{apple} → {apple}	app differs from apple	false
startsWith app	{apple} → {apple}	compare a=a, p=p, p=p	true
insert app	{apple} → {apple, app}	add full shorter word	null
search app	{apple, app} → {apple, app}	exact member found	true
all outputs	{apple, app}	constructor and inserts return null	[null,null,true,false,true,null,true]

Complexity Analysis

Time Complexity

O(nm)

Space Complexity

O(S+n)

Here n is the number of distinct stored words, m is the current query length, and S is their total character count. A prefix query takes O(nm) worst-case character comparisons. Insert and search take expected O(m) to hash a fresh string, not unconditional O(1); implementations may cache string hashes. Adversarial hash collisions can worsen membership costs. The set stores O(n) references and retains O(S) input characters rather than copying each word. A single operation uses O(1) extra workspace beyond the retained set.

Code

Solution.java

1import java.util.HashSet;2import java.util.Set;3
4class Trie {5    private Set<String> words = new HashSet<>();6
7    public void insert(String word) {8        words.add(word);9    }10
11    public boolean search(String word) {12        return words.contains(word);13    }14
15    public boolean startsWith(String prefix) {16        // Only full words are stored, so prefix lookup must examine candidates.17        for (String word : words) {18            if (word.startsWith(prefix)) {19                return true;20            }21        }22        return false;23    }24}

Hints

Hint 1

Picture each word as a path from the root, with one node per letter and shared prefixes sharing nodes.

Hint 2

A boolean on each node records whether some inserted word ends there, which is what separates search from startsWith.

Hint 3

Both lookups walk the same path letter by letter; only the final check on the flag differs.

Edge Cases

A word that is a prefix of another word, such as app inside apple, which needs the flag to tell them apart.
A query longer than any inserted word that still follows a live prefix for a while.
Inserting the same word twice, which should simply set the flag again without duplicating nodes.
Queries on an empty structure are false because inputs are nonempty; a 2000-character word is handled iteratively, without recursion.
Separate Trie instances must own separate roots or sets, so inserting into one does not affect another.

Common Mistakes and Interview Tips

Forgetting to set the word-end flag on insert, so every search returns false.
Returning true from search whenever the path exists, without verifying the word-end flag.
Creating a fresh chain for a word that shares a prefix instead of reusing the existing nodes.
Calling hash-set insertion constant time without accounting for hashing a previously unseen string.
Putting root or children in shared static/class state, which leaks stored words between instances.

Key Takeaway

When many strings share prefixes, store one node per character and answer word and prefix queries with a single walk whose cost depends only on the query length.