Autocomplete needs a data structure that shares work across words with common prefixes. That structure is a trie - a tree where each edge is a character. Today you define its node and create an empty engine that knows it holds nothing yet.
Define a trie node keyed by character and create an empty trie that reports zero words.
A trie (pronounced “try”, from retrieval) is a tree that stores strings by
their characters: the root is the empty string, and following an edge labelled
c moves to the node for every word that has c at that position. Words that
share a prefix share the nodes for that prefix, which is exactly what makes a trie
the natural home for autocomplete - the completions of ca are everything in the
subtree hanging off the c-then-a node.
Today is deliberately tiny: one node type whose children map is keyed by the
next character, an end flag marking where a word finishes, and the Trie that
owns the root and a running word count. The weight field is along for the ride -
later lessons rank completions by it, so we reserve it now and leave it 0. Every
later lesson grows this same tree.
// one node per character position; children keyed by the next runetype node struct {children map[rune]*nodeend bool // true when a word ends exactly hereweight int // a term's rank score; unused until later, leave 0}type Trie struct {root *nodesize int}func NewTrie() *Trie { return &Trie{root: &node{children: map[rune]*node{}}} }func (t *Trie) Len() int { return t.size }