Tries and prefix search

A command palette suggests names as the user types. With a few commands, filtering the whole list is fine. As the same dictionary serves many prefix queries, repeatedly checking every name becomes the work worth avoiding.

A trie shares the beginning of words as paths. Following the typed prefix reaches the relevant subtree, but the index still needs to distinguish a complete command from a path that only leads to a longer one.

Completing a prefix without scanning every word

A trie indexes shared prefixes as paths. A terminal marker is independent of having children: a complete word may also prefix another word. Empty words terminate at the root.

Marking complete words along a shared path

Insert car, cart, and cat. They share c → a, while car ends at a node that also leads onward to cart. Mark that node terminal. For prefix ca, visit child characters in sorted order and emit a terminal word before its longer descendants. With a limit of two, stop after car, cart rather than construct every completion.

type PrefixNode struct { Terminal bool; Children map[rune]*PrefixNode }
root := &PrefixNode{Children: map[rune]*PrefixNode{}}
fmt.Println(root.Terminal)

Paying for the completions you return

A map does not provide lexicographic traversal; collect and sort child rune keys before visiting them. Stop enumeration at the requested limit instead of building every completion first. Construction costs total input length and node storage; a trie helps repeated prefix queries, while one small query may favor a direct scan.

Building the trie costs expected O(L) map operations for L input symbols, with up to O(L) nodes. Following a prefix costs O(p), then enumeration also pays for visited nodes, child ordering, and returned text. The one-call exercise rebuilds the index; repeated-query savings need a reused structure.

A command palette can reuse its trie across keystrokes, which is where the preparation starts to pay off.