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 stores a path per code-point prefix. A terminal flag distinguishes a complete word from a prefix that only leads to longer words. Without that flag, inserting cold and colder makes it impossible to distinguish whether cold is independently present.

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.

struct TrieNode {bool terminal=false;std::map<char32_t,std::unique_ptr<TrieNode>> children;};
// Ordered child keys make depth-first emission lexicographic.

Paying for the completions you return

Following the query prefix avoids exploring unrelated branches, then a depth-first traversal emits a terminal word before longer descendants. Duplicate inserts set the same terminal flag and do not duplicate results. Empty words terminate at the root. Building the trie still costs work proportional to all input code points; querying one prefix does not erase that cost. An ordered child map adds logarithmic branching cost; a hash map would need sorted traversal keys. Stop once the output limit is reached and preserve the original word collection.

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.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged. Text ordering follows Unicode code points (Text) or the documented UTF-8 identifier order (std::string).

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