Implement Trie Prefix Tree

Asked byAmazonGoogleTwitterMicrosoftSnapchatApple

Problem

Implement a Trie (prefix tree) with insert, search, and startsWith operations — insert adds a word, search checks whether an exact word was inserted, and startsWith checks whether any inserted word begins with a given prefix.

Examples

Example 1

Input:insert("apple"); search("apple")

Output:true

Example 2

Input:search("app"); startsWith("app")

Output:false, true

"app" was never inserted, but it is a prefix of "apple".

Constraints

1 <= word.length, prefix.length <= 2000
Words and prefixes consist of lowercase English letters.

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Tries pattern

A trie (prefix tree) stores strings character by character along tree edges, so words sharing a prefix share the same path. It turns "does any word start with this prefix?" into a walk proportional to the prefix length instead of a scan of every word.

Look for this pattern when

You're repeatedly checking prefixes (autocomplete, spell-check, word search on a grid).
You need to store a large dictionary of words and query it efficiently by prefix.

Read the full Tries guide →

Video walkthroughs

Original problem on LeetCode ↗