Lesson 19.2 · Trie

Prefix Counts and Autocomplete

Store how many words pass through each node, or the best few suggestions at each node, and prefix questions become one walk.

10 min

Think of it like this

A shop's search box: after you type "ap" it already knows there are 4 matching products and shows the top 3, without reading the whole catalogue.

1.Extra data on the nodes

Add int pass to each node and increment it on every node an insert walks through. Then countPrefix(p) is the pass value at the end of p's path. Similar extras: the number of words ending here (duplicates), or a short sorted list of suggestions per node for autocomplete.

Main.java

public class Main {
    static class Node { Node[] next = new Node[26]; int pass; }
    static Node root = new Node();

    static void insert(String w) {
        Node n = root;
        for (char c : w.toCharArray()) {
            if (n.next[c - 'a'] == null) n.next[c - 'a'] = new Node();
            n = n.next[c - 'a'];
            n.pass++;
        }
    }

    static int countPrefix(String p) {
        Node n = root;
        for (char c : p.toCharArray()) {
            n = n.next[c - 'a'];
            if (n == null) return 0;
        }
        return n.pass;
    }

    public static void main(String[] args) {
        for (String w : new String[]{"apple", "app", "apply", "ape", "bat"}) insert(w);
        for (String p : new String[]{"ap", "app", "b", "c"}) System.out.println(p + " -> " + countPrefix(p));
    }
}

Output

ap -> 4
app -> 3
b -> 1
c -> 0

Remember

Counts on nodes answer "how many words start with p" in O(|p|).
Sorted insertion + a cap of k per node gives autocomplete.

Common mistakes

Counting at the root (every word passes it).

Command Palette

Prefix Counts and Autocomplete

1.Extra data on the nodes