Autocomplete System using Trie in C++

An autocomplete system predicts the completion of a word as a user types. This system can be efficiently implemented using a Trie (Prefix Tree). A Trie is a tree-like data structure that stores strings in a way that facilitates quick retrieval based on prefixes, making it an ideal choice for implementing autocomplete functionality.

Program Structure

The C++ implementation of an Autocomplete System using a Trie will include:

1. Trie Node Structure: Defining the structure of a node in the Trie.
2. Trie Class: Implementing the Trie with functions for inserting words and searching for words based on a given prefix.
3. Autocomplete Functionality: Implementing the autocomplete function that returns all possible completions of a given prefix.
4. Example Usage: Demonstrating the insertion of words and the autocomplete feature.

Code Implementation

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

class TrieNode {
public:
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;

    TrieNode() : isEndOfWord(false) {}
};

class Trie {
private:
    TrieNode* root;

    void autocompleteHelper(TrieNode* node, std::string currentPrefix, std::vector<std::string> &results) {
        if (node->isEndOfWord) {
            results.push_back(currentPrefix);
        }

        for (auto &child : node->children) {
            autocompleteHelper(child.second, currentPrefix + child.first, results);
        }
    }

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(const std::string &word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEndOfWord = true;
    }

    std::vector<std::string> autocomplete(const std::string &prefix) {
        TrieNode* node = root;
        std::vector<std::string> results;

        for (char ch : prefix) {
            if (node->children.find(ch) == node->children.end()) {
                return results; // Prefix not found
            }
            node = node->children[ch];
        }

        autocompleteHelper(node, prefix, results);
        return results;
    }
};

// Main function to demonstrate the Autocomplete System using Trie
int main() {
    Trie trie;
    trie.insert("hello");
    trie.insert("hell");
    trie.insert("heaven");
    trie.insert("heavy");

    std::string prefix = "he";
    std::vector<std::string> suggestions = trie.autocomplete(prefix);

    std::cout << "Autocomplete suggestions for prefix '" << prefix << "':" << std::endl;
    for (const std::string &suggestion : suggestions) {
        std::cout << suggestion << std::endl;
    }

    return 0;
}

Explanation

Trie Node Structure

The TrieNode class represents a node in the Trie. It contains:

• children: An unordered map that stores pointers to the child nodes, where the key is the character and the value is a pointer to the corresponding child node.
• isEndOfWord: A boolean flag that indicates if the node marks the end of a word.

Trie Class

The Trie class manages the overall Trie structure and provides functions to insert words and search for autocomplete suggestions. The key functions include:

• insert(): Adds a word to the Trie by creating a new node for each character that doesn’t already exist in the Trie.
• autocomplete(): Takes a prefix as input and returns a list of all possible completions by traversing the Trie from the last node of the prefix.

Autocomplete Functionality

The autocompleteHelper() function is a recursive helper function that collects all words that start with the given prefix. It traverses the Trie starting from the node that matches the last character of the prefix, and accumulates the results in a vector.

Example Usage

In the main() function, the program demonstrates the usage of the Trie for an autocomplete system. It inserts several words into the Trie, then searches for all words that start with the prefix “he” and displays the suggestions.

Conclusion

The Trie is an efficient data structure for implementing an autocomplete system. It allows for quick insertion and retrieval of words based on their prefixes, making it ideal for applications such as search engines, text editors, and mobile keyboards. This C++ implementation covers the essential functionality of a Trie-based autocomplete system, including word insertion and prefix-based suggestion retrieval.