Step 6 of 6

Challenge: a trie for autocomplete

A trie (from retrieval, often said "try") stores strings character by character. Each node has up to 26 children, one per letter, and a flag marking where a complete word ends. Words that share a prefix share the path for it:

root
 └ c
   └ a
     ├ r *        "car"
     │ └ t *      "cart"
     └ t *        "cat"

So "which words start with ca?" only needs to walk two nodes, then look below, no matter how many other words the trie holds. Search boxes, spell checkers and network routers use tries.

#include <array>
#include <iostream>
#include <memory>
#include <string>

struct Node {
    std::array<std::unique_ptr<Node>, 26> next;   // one slot per letter
    bool end = false;
};

void insert(Node& root, const std::string& w) {
    Node* n = &root;
    for (char c : w) {
        auto& child = n->next[c - 'a'];
        if (!child) child = std::make_unique<Node>();
        n = child.get();
    }
    n->end = true;
}

void print_all(const Node& n, std::string& prefix) {
    if (n.end) std::cout << prefix << " ";
    for (int i = 0; i < 26; i++) {                 // 'a' to 'z': alphabetical order
        if (n.next[i]) {
            prefix.push_back(char('a' + i));
            print_all(*n.next[i], prefix);
            prefix.pop_back();                     // undo before trying the next letter
        }
    }
}

int main() {
    Node root;
    for (const char* w : {"cat", "car", "cart", "dog", "do"}) insert(root, w);
    std::string prefix;
    print_all(root, prefix);
    std::cout << "\n";
}

car cart cat do dog 

How it works

• c - 'a' turns a lowercase letter into an index from 0 to 25.
• insert walks down, creating missing nodes on the way, and marks the last one as a word end. "do" and "dog" share nodes; only the end flags differ.
• print_all is a depth-first walk that builds the current word in prefix, adding a letter before going down and removing it after coming back. Visiting children from 'a' to 'z' prints the words sorted.

Your task's extras

• count_prefix: add an int pass counter to each node, and increment it on every node you pass through during insert. Then the answer is the counter of the node at the end of the prefix. To count a repeated word only once, check contains first and skip the insert.
• complete: walk to the prefix's node (no node means no words), then do the depth-first walk above from there, collecting words into a vector, and stop once you have limit.

Your turn: write class Trie for lowercase words:

• void insert(const std::string& w)
• bool contains(const std::string& w) const: exact word
• int count_prefix(const std::string& p) const: how many inserted words start with p (store a counter in every node you pass during insert)
• std::vector<std::string> complete(const std::string& p, std::size_t limit) const: up to limit words with that prefix, in alphabetical order (a depth-first walk visiting children 'a' to 'z' produces them sorted)

Inserting the same word twice counts it once.

Previous: A binary heap by hand