Trie

Trie

Introduction

A trie is a data structure for storing strings. Its main idea is simple: words with the same beginning should share the same path.

For example, the words app, apple, and ape all begin with a, so we store that first character only once. They also share the prefix ap, so they follow the same path for two characters. The paths separate only when the words become different.

This makes a trie useful when we repeatedly insert words, search for a complete word, or ask how many stored words begin with a given prefix. Each operation follows the characters of one string from left to right, so its time depends on the string length rather than on the number of stored words.

Problem or motivation

We maintain a collection of non-empty strings consisting of lowercase English letters. Equal strings may be inserted several times, and every copy is counted separately. We need to process three types of operations:

• 1 s — insert the string s;
• 2 s — print how many inserted strings are exactly equal to s;
• 3 s — print how many inserted strings begin with s.

Suppose we insert app, apple, ape, and app. Then app occurs exactly twice, while three stored words begin with app: the two copies of app and the word apple. All four words begin with ap.

This task contains two different questions. An exact-word query asks whether a word ends at a certain point. A prefix query also counts longer words that continue after that point. Our trie must keep enough information to answer both.

Naive approach

The simplest solution stores every inserted string in a vector. To answer a query, we scan the whole vector and compare the query with every stored word.

If there are $n$ stored words and a query string has length $m$, one query may take time. Most of this work is repeated. For example, when many words begin with , we compare the same first seven characters again for every word and every prefix query.