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: each edge consumes one code point and each node represents the path reaching it. Exact completion queries follow the requested prefix before exploring matching suffixes. The baseline instead filters the full input, deduplicates matches and sorts them on every query.

A terminal marker distinguishes a complete word from a path that only leads to longer words. Inserting cold and colder must still remember that cold itself is a valid result.

Marking complete words along a shared path

Build the trie from code points, setting a terminal flag at each word's final node. Duplicate words reach the same terminal and add no additional result. The empty word terminates at the root, so an empty prefix can include it.

After following the query prefix, visit terminal content before descendants, and traverse child keys in ascending code-point order. That ordering emits a word before its longer extensions and yields lexicographic completion order. Stop after the output limit, but include the full trie construction cost in performance claims.

Use Map children rather than object properties when representing arbitrary code-point edges. Map insertion order alone is not the required sorted order. The supplied compareText helper compares whole strings by code points; use it to sort words or child-symbol keys. Default UTF-16 sort and localeCompare are different policies. Copy collections before sorting.

import { compareText } from "./exercise.mjs";
const children = new Map([["😀", {}], ["", {}], ["a", {}]]);
console.log([...children.keys()].sort(compareText)); // ["a", "", "😀"]
const terminalAtRoot = true;
console.log(terminalAtRoot); // true: the empty word may be stored

Paying for the completions you return

Let L be total input code points. Construction costs O(L) expected Map work and O(L) nodes, ignoring text comparison costs. Querying a prefix avoids unrelated subtrees, but sorting child keys and producing returned words still cost work. Building a trie from scratch for one small query may be slower than filtering; repeated prefix queries make reuse more valuable.

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