Step 6 of 6
Challenge: a trie for autocomplete
A trie (prefix tree) stores strings character by character: each node has up to 26 children, one per letter, and a flag marking where a word ends. Every word sharing a prefix shares that path, so "how many words start with de_?" takes O(length of the prefix), no matter how many words there are. Search boxes, spell checkers and routers use tries.
Your turn: write class Trie for lowercase words:
void insert(const std::string& w)bool contains(const std::string& w) const: exact wordint 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 tolimitwords 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.