LESSON 25 · PATTERN GUIDE

Trie

Store words by shared prefixes to support efficient prefix search and dictionary lookup.

FIRST, LEARN THE PATTERNEach edge represents a character; nodes can mark the end of a complete word. Search time depends mainly on the query length.

The task repeatedly checks prefixes, autocomplete suggestions, or a dictionary of words.

How to approach it

Walk or create one child per character. Mark word endings separately from mere prefix nodes.

Watch out for

A trie can use substantial memory, especially with a wide child array; consider maps or compressed representations.

A CLOSER EXPLANATION

Words with a shared prefix share the same path from the root. A node needs an end-of-word marker because a path can be a valid prefix without being a stored word. Lookup and prefix checks take time proportional to the number of characters searched.

NOW YOU TRY

Practice question

After inserting 'cat' and 'car', does the trie contain the prefix 'ca'? Is 'ca' itself a complete word?

EXAMPLEWords = ['cat', 'car']Give your answer before revealing the explanation.

Show a hint

A prefix node and an end-of-word marker represent different facts.

Show an answer

Prefix 'ca' exists; 'ca' is not a complete word unless it was inserted too.

CONNECT IT TO REAL LIFE

Trie at work

A phone keyboard has saved contacts 'Maya', 'Mayank', and 'Ravi'. Which suggestions should appear after the user types 'May'?

Show one possible approach

Maya and Mayank. Walk the trie through M-a-y, then list stored words reachable below that prefix node.

Practice next

Use these problem IDs to find additional practice for this pattern:

2082112126486771268