How do I implement trie and prefix matching in C++?

A Trie (pronounced as "try") is a tree-like data structure that is used to efficiently store a dynamic set of strings, where keys are usually strings. It is especially useful for implementing auto-complete functionalities and prefix matching. Below, you will find a simple implementation of a Trie in C++ along with a demonstration of how to search for strings with specific prefixes.

Trie Implementation in C++


#include 
#include 
#include 
using namespace std;

class TrieNode {
public:
    unordered_map children;
    bool isEndOfWord;

    TrieNode() {
        isEndOfWord = false;
    }
};

class Trie {
private:
    TrieNode* root;

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

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

    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return node->isEndOfWord;
    }

    vector startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end()) {
                return {};
            }
            node = node->children[c];
        }
        return traverseNode(node, prefix);
    }

private:
    vector traverseNode(TrieNode* node, string prefix) {
        vector results;
        if (node->isEndOfWord) {
            results.push_back(prefix);
        }
        for (auto& pair : node->children) {
            results = vector(results.begin(), results.end());
            results = vector(results.end(), traverseNode(pair.second, prefix + pair.first));
        }
        return results;
    }
};

// Example Usage
int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    trie.insert("bat");
    trie.insert("ball");

    cout << "Search 'app': " << trie.search("app") << endl; // Output: 1 (true)
    cout << "Search 'bat': " << trie.search("bat") << endl; // Output: 1 (true)
    cout << "Search 'ball': " << trie.search("bal") << endl; // Output: 0 (false)
    
    vector suggestions = trie.startsWith("ba");
    cout << "Suggestions for 'ba': ";
    for (const string& s : suggestions) {
        cout << s << " ";
    }
    cout << endl; // Output: bat ball

    return 0;
}

How do I implement trie and prefix matching in C++?

Trie Implementation in C++

Popular Topics

Recent Languages

How do I implement trie and prefix matching in C++?

Trie Implementation in C++

Related Questions

Popular Topics

Recent Languages