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

Complete an exact prefix with unique words in a canonical order and bounded result count. A prefix may itself be a stored word and still have longer descendants.

Filtering and sorting every word is a valid baseline. A trie shares prefix paths, but it needs a terminal marker separate from child existence. Stopping at the first node with children would omit words that are also prefixes.

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.

A trie separates the prefix walk from suffix enumeration. A terminal marker distinguishes a stored word from an internal prefix, including the empty word at the root. Sort child characters while traversing and stop at the limit. Include index construction O(total input characters); result enumeration also costs emitted characters, not merely result count.

Terminality and continuation are independent facts at one trie position:

import java.util.*;

class Example {
    public static void main(String[] args) {
        record PrefixState(boolean terminal, SortedSet<Character> children) {}
        var atA = new PrefixState(true, new TreeSet<>(List.of('b', 'c')));
        assert atA.terminal(); // "a" itself is stored
        assert atA.children().contains('b'); // "ab" can also be stored
        assert atA.children().size() == 2;
    }
}

The terminal must be emitted before longer suffixes in lexical order. Traversal also needs sorted children and an early limit check. Building the index still costs the total input character count, even if the returned completion list is short.

Paying for the completions you return

Tries suit repeated prefix queries, lexical indexes, and autocomplete-like tasks when shared prefixes justify construction cost. A one-off query over a tiny list may be simpler with filtering and sorting.

Return at most limit distinct words starting with the exact case-sensitive prefix, in Java String.compareTo order. Empty strings/prefixes are valid, limit zero returns empty, negative limit raises IllegalArgumentException. Final must build a trie; prototype may filter/deduplicate/sort.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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