https://leetcode.com/problems/search-suggestions-system

type TrieNode = {
    word?: string;
} & {
    [letter: string]: TrieNode | boolean;
}

const targetWords = 3;

function suggestedProducts(products: string[], searchWord: string): string[][] {
    const root: TrieNode = { isWord: false };
    for(const product of products) {
        let node = root;
        for(const ch of product) {
            if (!node[ch]) {
                node[ch] = { };
            }
            node = node[ch] as TrieNode;
        }
        node.word = product;
    }
    function fillWords(node: TrieNode, words: string[]) {
        if (!node) return;
        if (node.word) {
            words.push(node.word);
        }
        // TODO: we could probably save some time by pre-sorting these
        for(const ix of Object.keys(node).sort()) {
            if (words.length >= targetWords) break;
            if (ix.length === 1) {
                fillWords(node[ix] as TrieNode, words);
            }
        }
    }

    const results: string[][] = [];
    {
        let node = root;
        for (const ch of searchWord) {
            const result: string[] = [];
            if (node) {
                node = node[ch] as TrieNode;
                fillWords(node, result);
            }
            results.push(result);
        }
    }

    return results;
};