By Bernard Adjanor Katamanso

The Problem

Autocomplete is everywhere. Start typing in a search box, and suggestions appear instantly. But how do you build this efficiently?

The core challenge:

Given a string and a dictionary of words, return all words that start with that word.

Example:

word = "de"
dictionary = ["dog", "deer", "deal"]
output = ["deer", "deal"]

This seems straightforward, but when your dataset grows to thousands or millions of words, naive approaches break down.

My First Attempts

Initially, I looped through all words and checked each one using strings.HasPrefix:

func findWords(prefix string, words []string) []string {
    var results []string
    for _, word := range words {
        if strings.HasPrefix(word, prefix) {
            results = append(results, word)
        }
    }
    return results
}

The problem: Every search scans the entire dictionary. Time complexity: O(n × p), where n is the number of words and p is the prefix length.

With 100,000 words, a simple search could check all 100,000 entries. That's too slow for real-time autocomplete.

I tried grouping words by their first character using a map, which helped slightly but still wasn't efficient enough for prefix searches.

Why a Trie?

A Trie (pronounced "try") is a tree structure designed specifically for prefix-based operations. Here's why it's perfect for autocomplete:

1. Shared prefixes: Common beginnings are stored only once
2. Fast lookups: Navigate directly to the prefix node without checking irrelevant words
3. Efficient collection: Gather all matching words by traversing from the prefix node

Time complexity improves dramatically to O(p + k), where: