Implement Trie (Prefix Tree)

Problem

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Solution Approach

Expected Time complexity: $O(n)$

Click - to see solution code

C++

struct Node {
    unordered_map<char, Node*> mp;
    char c;
    bool terminal;
    Node(char val) {
        c = val;
        terminal = false;
    }
};

class Trie {
   public:
    Node* root;

    Trie() { root = new Node('*'); }

    void insert(string word) {
        int n = word.size();
        Node* temp = root;
        for (int i = 0; i < n; i++) {
            if (temp->mp.find(word[i]) == temp->mp.end()) {
                Node* newNode = new Node(word[i]);
                temp->mp[word[i]] = newNode;
                temp = newNode;
            } else
                temp = temp->mp[word[i]];
        }
        temp->terminal = true;
    }

    bool search(string word) {
        Node* temp = root;
        int n = word.size();
        for (int i = 0; i < n; i++) {
            if (temp->mp.find(word[i]) == temp->mp.end()) return false;
            temp = temp->mp[word[i]];
        }
        return temp->terminal;
    }

    bool startsWith(string word) {
        Node* temp = root;
        int n = word.size();
        for (int i = 0; i < n; i++) {
            if (temp->mp.find(word[i]) == temp->mp.end()) return false;
            temp = temp->mp[word[i]];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */