PK

PKBytes

Explore tracks
Chapter 28: Tries, Prefix Trees and Dictionary Structures
28.03Intermediate / Advanced5 topics16 min5 interactive animations

Prefix problems

The classic things a trie answers: autocomplete, longest common prefix, prefix counts, ranked suggestions and add-and-search dictionaries.

Learning goals

  • List every word that starts with a prefix, in alphabetical order
  • Compute the longest common prefix of a set of words
  • Answer 'how many words start with p' in O(length of p) using pass counts
  • Build ranked suggestions and a dictionary that supports a '.' wildcard

Prerequisites

Trie fundamentalsTrie implementationRecursion

Search boxes, phone keyboards, spell checkers and IP routing tables all ask the same question: what do I know that begins with this? A trie answers by walking to the prefix and reading off everything below it.

28.03.1

Autocomplete

Autocomplete has two steps: walk to the node for the typed prefix, then collect the words in the subtree below it. If the children are visited in alphabetical order, the words come out alphabetically for free, with no sort. The cost is O(length of the prefix + size of the subtree), and a limit stops the walk early when only the first few suggestions are needed.

Run the animation with the question "Autocomplete: every word with the prefix" and the prefix ca: it finds car, cart and cat. With the preset "Prefix with no match", the walk breaks at the x of cx and returns nothing.

Java
1class Trie {
2    private static class Node {
3        Node[] next = new Node[26];
4        boolean end;
5    }
6    private final Node root = new Node();
7    void insert(String word) {
8        Node n = root;
9        for (char c : word.toCharArray()) {
10            int i = c - 'a';
11            if (n.next[i] == null) n.next[i] = new Node();
12            n = n.next[i];
13        }
14        n.end = true;
15    }
16    List<String> autocomplete(String prefix, int limit) {
17        List<String> out = new ArrayList<>();
18        Node n = root;
19        for (char c : prefix.toCharArray()) {
20            n = n.next[c - 'a'];
21            if (n == null) return out;           // nothing starts with this prefix
22        }
23        collect(n, new StringBuilder(prefix), out, limit);
24        return out;
25    }
26    private void collect(Node n, StringBuilder sb, List<String> out, int limit) {
27        if (out.size() >= limit) return;
28        if (n.end) out.add(sb.toString());       // a word ends here
29        for (int c = 0; c < 26 && out.size() < limit; c++) {     // alphabetical order for free
30            if (n.next[c] == null) continue;
31            sb.append((char) ('a' + c));
32            collect(n.next[c], sb, out, limit);
33            sb.deleteCharAt(sb.length() - 1);
34        }
35    }
36}

Prefix queries: autocomplete, prefix counts, longest common prefix

Interactive · edit the input

Your input

Try

trie · 9 nodes

root
c
a
r

word

t

word

t

word

d
o

word

g

word

Being followedMatchDead endA word ends here
Setup

Autocomplete = walk to the prefix node, then collect every word in its subtree in alphabetical order.

Step 1 / 8
Java
1private Node walk(String s) {                          // node for a prefix, or null
2    Node n = root;
3    for (char c : s.toCharArray()) { n = n.next[c - 'a']; if (n == null) return null; }
4    return n;
5}
6int countPrefix(String p) { Node n = walk(p); return n == null ? 0 : n.pass; }   // insert did pass++ on every node it visits
7List<String> autocomplete(String p) {
8    List<String> out = new ArrayList<>();
9    Node n = walk(p);
10    if (n != null) collect(n, new StringBuilder(p), out);
11    return out;
12}
13private void collect(Node n, StringBuilder sb, List<String> out) {
14    if (n.end) out.add(sb.toString());                  // a word ends here
15    for (int c = 0; c < 26; c++) {                      // alphabetical order for free
16        if (n.next[c] == null) continue;
17        sb.append((char) ('a' + c));
18        collect(n.next[c], sb, out);
19        sb.deleteCharAt(sb.length() - 1);
20    }
21}
22String longestCommonPrefix() {
23    StringBuilder sb = new StringBuilder();
24    Node n = root;
25    while (!n.end && n.kids == 1) {                     // one way forward and no word stops here
26        int c = onlyChild(n);
27        sb.append((char) ('a' + c));
28        n = n.next[c];
29    }
30    return sb.toString();
31}

Live state

0 nodes visited

words

5

No condition evaluated on this step
Execution trace (dry run table)Show 8 steps
StepLineStateWhat happens
1L1words=5Autocomplete = walk to the prefix node, then collect every word in its subtree in alphabetical order.
2L3prefix="c" pass=3Follow 'c': 3 words run through this node.
3L3prefix="ca" pass=3Follow 'a': 3 words run through this node.
4L15path="ca"Visit "ca": not a word, keep going down.
5L14word="car" found=1A word ends here: add "car" to the result.
6L14word="cart" found=2A word ends here: add "cart" to the result.
7L14word="cat" found=3A word ends here: add "cat" to the result.
8L11return=["car", "cart", "cat"]3 completions for "ca": "car", "cart", "cat". Cost O(length of the prefix + size of the subtree).
28.03.2

Common prefixes

The longest common prefix of a set of words is the path from the root that every word follows. Walk down from the root while the current node has exactly one child and no word ends there: the first node with two or more children (the words diverge) or with an end flag (a word stops) marks the end of the common prefix.

Choose the preset "Longest common prefix" (flower flow flight): the path f, l is the only way until the node fl splits into o and i, so the answer is fl. With dog car race the root already has three children and the answer is empty. For a one-off question a direct comparison of the strings is simpler; the trie pays off when the same word set is queried repeatedly.

Java
1class LcpTrie {
2    private static class Node {
3        Node[] next = new Node[26];
4        boolean end;
5        int kids;
6    }
7    private final Node root = new Node();
8    void insert(String word) {
9        Node n = root;
10        for (char c : word.toCharArray()) {
11            int i = c - 'a';
12            if (n.next[i] == null) { n.next[i] = new Node(); n.kids++; }
13            n = n.next[i];
14        }
15        n.end = true;
16    }
17    String longestCommonPrefix() {
18        StringBuilder sb = new StringBuilder();
19        Node n = root;
20        while (!n.end && n.kids == 1) {          // one way forward and no word stops here
21            int c = 0;
22            while (n.next[c] == null) c++;       // the only child
23            sb.append((char) ('a' + c));
24            n = n.next[c];
25        }
26        return sb.toString();
27    }
28}

Prefix queries: autocomplete, prefix counts, longest common prefix

Interactive · edit the input

Your input

Try

trie · 9 nodes

root
c
a
r

word

t

word

t

word

d
o

word

g

word

Being followedMatchDead endA word ends here
Setup

Autocomplete = walk to the prefix node, then collect every word in its subtree in alphabetical order.

Step 1 / 8
Java
1private Node walk(String s) {                          // node for a prefix, or null
2    Node n = root;
3    for (char c : s.toCharArray()) { n = n.next[c - 'a']; if (n == null) return null; }
4    return n;
5}
6int countPrefix(String p) { Node n = walk(p); return n == null ? 0 : n.pass; }   // insert did pass++ on every node it visits
7List<String> autocomplete(String p) {
8    List<String> out = new ArrayList<>();
9    Node n = walk(p);
10    if (n != null) collect(n, new StringBuilder(p), out);
11    return out;
12}
13private void collect(Node n, StringBuilder sb, List<String> out) {
14    if (n.end) out.add(sb.toString());                  // a word ends here
15    for (int c = 0; c < 26; c++) {                      // alphabetical order for free
16        if (n.next[c] == null) continue;
17        sb.append((char) ('a' + c));
18        collect(n.next[c], sb, out);
19        sb.deleteCharAt(sb.length() - 1);
20    }
21}
22String longestCommonPrefix() {
23    StringBuilder sb = new StringBuilder();
24    Node n = root;
25    while (!n.end && n.kids == 1) {                     // one way forward and no word stops here
26        int c = onlyChild(n);
27        sb.append((char) ('a' + c));
28        n = n.next[c];
29    }
30    return sb.toString();
31}

Live state

0 nodes visited

words

5

No condition evaluated on this step
Execution trace (dry run table)Show 8 steps
StepLineStateWhat happens
1L1words=5Autocomplete = walk to the prefix node, then collect every word in its subtree in alphabetical order.
2L3prefix="c" pass=3Follow 'c': 3 words run through this node.
3L3prefix="ca" pass=3Follow 'a': 3 words run through this node.
4L15path="ca"Visit "ca": not a word, keep going down.
5L14word="car" found=1A word ends here: add "car" to the result.
6L14word="cart" found=2A word ends here: add "cart" to the result.
7L14word="cat" found=3A word ends here: add "cat" to the result.
8L11return=["car", "cart", "cat"]3 completions for "ca": "car", "cart", "cat". Cost O(length of the prefix + size of the subtree).
28.03.3

Prefix counts

To count the words that start with a prefix, keep a pass counter on every node: the number of words whose path goes through it. insert increments the counter of each node it visits, so a prefix count is one lookup: walk to the prefix node and read its counter. The answer does not depend on how many words match.

Choose the question "How many words start with the prefix" with the preset "Count words with prefix": in apple app apt art the prefix ap has the node with pass 3. The counts appear as ×n under each letter. Counting with a plain DFS would cost the size of the subtree; the stored counter makes it O(length of the prefix).

Java
1class PrefixCounter {
2    private static class Node {
3        Node[] next = new Node[26];
4        int pass;                                // words that go through this node
5        int ends;                                // words that end exactly here
6    }
7    private final Node root = new Node();
8    void insert(String word) {
9        Node n = root;
10        for (char c : word.toCharArray()) {
11            int i = c - 'a';
12            if (n.next[i] == null) n.next[i] = new Node();
13            n = n.next[i];
14            n.pass++;
15        }
16        n.ends++;
17    }
18    int countPrefix(String prefix) {             // words that start with prefix
19        Node n = root;
20        for (char c : prefix.toCharArray()) {
21            n = n.next[c - 'a'];
22            if (n == null) return 0;
23        }
24        return n.pass;
25    }
26    int countWords(String word) {                // words equal to word
27        Node n = root;
28        for (char c : word.toCharArray()) {
29            n = n.next[c - 'a'];
30            if (n == null) return 0;
31        }
32        return n.ends;
33    }
34}

Prefix queries: autocomplete, prefix counts, longest common prefix

Interactive · edit the input

Your input

Try

trie · 9 nodes

root
c
a
r

word

t

word

t

word

d
o

word

g

word

Being followedMatchDead endA word ends here
Setup

Autocomplete = walk to the prefix node, then collect every word in its subtree in alphabetical order.

Step 1 / 8
Java
1private Node walk(String s) {                          // node for a prefix, or null
2    Node n = root;
3    for (char c : s.toCharArray()) { n = n.next[c - 'a']; if (n == null) return null; }
4    return n;
5}
6int countPrefix(String p) { Node n = walk(p); return n == null ? 0 : n.pass; }   // insert did pass++ on every node it visits
7List<String> autocomplete(String p) {
8    List<String> out = new ArrayList<>();
9    Node n = walk(p);
10    if (n != null) collect(n, new StringBuilder(p), out);
11    return out;
12}
13private void collect(Node n, StringBuilder sb, List<String> out) {
14    if (n.end) out.add(sb.toString());                  // a word ends here
15    for (int c = 0; c < 26; c++) {                      // alphabetical order for free
16        if (n.next[c] == null) continue;
17        sb.append((char) ('a' + c));
18        collect(n.next[c], sb, out);
19        sb.deleteCharAt(sb.length() - 1);
20    }
21}
22String longestCommonPrefix() {
23    StringBuilder sb = new StringBuilder();
24    Node n = root;
25    while (!n.end && n.kids == 1) {                     // one way forward and no word stops here
26        int c = onlyChild(n);
27        sb.append((char) ('a' + c));
28        n = n.next[c];
29    }
30    return sb.toString();
31}

Live state

0 nodes visited

words

5

No condition evaluated on this step
Execution trace (dry run table)Show 8 steps
StepLineStateWhat happens
1L1words=5Autocomplete = walk to the prefix node, then collect every word in its subtree in alphabetical order.
2L3prefix="c" pass=3Follow 'c': 3 words run through this node.
3L3prefix="ca" pass=3Follow 'a': 3 words run through this node.
4L15path="ca"Visit "ca": not a word, keep going down.
5L14word="car" found=1A word ends here: add "car" to the result.
6L14word="cart" found=2A word ends here: add "cart" to the result.
7L14word="cat" found=3A word ends here: add "cat" to the result.
8L11return=["car", "cart", "cat"]3 completions for "ca": "car", "cart", "cat". Cost O(length of the prefix + size of the subtree).
28.03.4

Contact directory

A contact directory or search-suggestion box shows a few ranked results after every keystroke. A common rule is: the three lexicographically smallest products that start with what was typed so far. Insert the products in sorted order and let every node remember the first three words that passed through it; then each keystroke is one edge followed and a stored list read.

Inserting in sorted order is what makes 'first three seen' equal to 'three smallest'. The total work is O(total length of all products) to build and O(length of the typed text) to answer all keystrokes, plus the size of the answers.

Java
1static List<List<String>> suggestedProducts(String[] products, String typed) {
2    class Node {
3        Node[] next = new Node[26];
4        List<String> top = new ArrayList<>();    // the first three words that pass through this node
5    }
6    String[] sorted = products.clone();
7    Arrays.sort(sorted);                         // so the first three seen are the three smallest
8    Node root = new Node();
9    for (String w : sorted) {
10        Node n = root;
11        for (char c : w.toCharArray()) {
12            int i = c - 'a';
13            if (n.next[i] == null) n.next[i] = new Node();
14            n = n.next[i];
15            if (n.top.size() < 3) n.top.add(w);
16        }
17    }
18    List<List<String>> out = new ArrayList<>();
19    Node n = root;
20    for (char c : typed.toCharArray()) {
21        if (n != null) n = n.next[c - 'a'];
22        out.add(n == null ? new ArrayList<>() : new ArrayList<>(n.top));
23    }
24    return out;
25}

Prefix queries: autocomplete, prefix counts, longest common prefix

Interactive · edit the input

Your input

Try

trie · 9 nodes

root
c
a
r

word

t

word

t

word

d
o

word

g

word

Being followedMatchDead endA word ends here
Setup

Autocomplete = walk to the prefix node, then collect every word in its subtree in alphabetical order.

Step 1 / 8
Java
1private Node walk(String s) {                          // node for a prefix, or null
2    Node n = root;
3    for (char c : s.toCharArray()) { n = n.next[c - 'a']; if (n == null) return null; }
4    return n;
5}
6int countPrefix(String p) { Node n = walk(p); return n == null ? 0 : n.pass; }   // insert did pass++ on every node it visits
7List<String> autocomplete(String p) {
8    List<String> out = new ArrayList<>();
9    Node n = walk(p);
10    if (n != null) collect(n, new StringBuilder(p), out);
11    return out;
12}
13private void collect(Node n, StringBuilder sb, List<String> out) {
14    if (n.end) out.add(sb.toString());                  // a word ends here
15    for (int c = 0; c < 26; c++) {                      // alphabetical order for free
16        if (n.next[c] == null) continue;
17        sb.append((char) ('a' + c));
18        collect(n.next[c], sb, out);
19        sb.deleteCharAt(sb.length() - 1);
20    }
21}
22String longestCommonPrefix() {
23    StringBuilder sb = new StringBuilder();
24    Node n = root;
25    while (!n.end && n.kids == 1) {                     // one way forward and no word stops here
26        int c = onlyChild(n);
27        sb.append((char) ('a' + c));
28        n = n.next[c];
29    }
30    return sb.toString();
31}

Live state

0 nodes visited

words

5

No condition evaluated on this step
Execution trace (dry run table)Show 8 steps
StepLineStateWhat happens
1L1words=5Autocomplete = walk to the prefix node, then collect every word in its subtree in alphabetical order.
2L3prefix="c" pass=3Follow 'c': 3 words run through this node.
3L3prefix="ca" pass=3Follow 'a': 3 words run through this node.
4L15path="ca"Visit "ca": not a word, keep going down.
5L14word="car" found=1A word ends here: add "car" to the result.
6L14word="cart" found=2A word ends here: add "cart" to the result.
7L14word="cat" found=3A word ends here: add "cat" to the result.
8L11return=["car", "cart", "cat"]3 completions for "ca": "car", "cart", "cat". Cost O(length of the prefix + size of the subtree).
28.03.5

Word dictionary

A word dictionary supports addWord(word) and search(pattern), where the pattern may contain . meaning 'any one letter'. A letter follows one edge; a dot tries every child, so the search becomes a depth-first search that returns true on the first match and backtracks on a dead end.

A pattern with no dots costs O(L), like a normal lookup. Each dot can multiply the work by the number of children, so in the worst case the search visits every node, but never more nodes than the trie has. Run the animation's "Dot in the middle" preset (b.d) and compare it with "No match" (b.t).

Java
1class WordDictionary {
2    private static class Node {
3        Node[] next = new Node[26];
4        boolean end;
5    }
6    private final Node root = new Node();
7    void addWord(String word) {
8        Node n = root;
9        for (char c : word.toCharArray()) {
10            int i = c - 'a';
11            if (n.next[i] == null) n.next[i] = new Node();
12            n = n.next[i];
13        }
14        n.end = true;
15    }
16    boolean search(String pattern) { return search(root, pattern, 0); }
17    private boolean search(Node n, String p, int i) {        // does any word below n match p[i..]?
18        if (n == null) return false;
19        if (i == p.length()) return n.end;
20        char c = p.charAt(i);
21        if (c != '.') return search(n.next[c - 'a'], p, i + 1);   // a letter: one way only
22        for (Node child : n.next)                                  // a dot: try every branch
23            if (child != null && search(child, p, i + 1)) return true;
24        return false;
25    }
26}

Wildcards: '.' search by DFS, and the prefix + suffix filter

Interactive · edit the input

Your input

Try

trie · 13 nodes

root
b
a
d

word

d
a
d

word

m
a
d

word

p
a
d

word

Being followedMatchDead endA word ends here
Setup

Search "b.d". A letter follows exactly one edge; a dot tries every child in turn, so the search becomes a DFS on the trie.

Step 1 / 7
Java
1boolean search(Node n, String p, int i) {               // does any word below n match p[i..]?
2    if (n == null) return false;
3    if (i == p.length()) return n.end;
4    char c = p.charAt(i);
5    if (c != '.') return search(n.next[c - 'a'], p, i + 1);   // a letter: one way only
6    for (Node child : n.next)                                  // a dot: try every branch
7        if (child != null && search(child, p, i + 1)) return true;
8    return false;
9}
10void addWord(String w) { for (int i = 0; i <= w.length(); i++) insert(w.substring(i) + "{" + w); }
11boolean hasPrefixSuffix(String pre, String suf) { return startsWith(suf + "{" + pre); }

Live state

0 nodes visited

pattern

"b.d"

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L1pattern="b.d"Search "b.d". A letter follows exactly one edge; a dot tries every child in turn, so the search becomes a DFS on the trie.
2L5i=1 char=bThe letter 'b' leaves one way: follow it.
3L6i=1 char=.A dot at position 1: try each of the 1 child in alphabetical order.
4L7i=2 branch=aTry the branch 'a'.
5L5i=3 char=dThe letter 'd' leaves one way: follow it.
6L3i=3 end=trueThe pattern is used up at a node where a word ends: match.
7L7return=true nodes visited=4search("b.d") = true after 4 node visits. It stops at the first match.

Practice ladder

Now try it yourself

Easy

  • Longest Common Prefix
  • Index Pairs of a String

Medium

  • Search Suggestions System
  • Design Add and Search Words Data Structure
  • Map Sum Pairs

Advanced

  • Design Search Autocomplete System
  • Word Squares

Key takeaways

  • Autocomplete = walk to the prefix node, then DFS the subtree in alphabetical order.
  • A pass counter on each node turns prefix counting into one O(length of the prefix) lookup.
  • Wildcards turn the search into a DFS that branches only at dots.