🌱 Keegan's Digital Garden

208. Implement Trie (Prefix Tree)

3 min read

📝 Problem Details

implement the following to construct a Trie class: Trie() constructor that initializes the object void insert(string word) inserts the string word into the Trie bool search(string word) returns true or false if the word exists in the Trie bool startsWith(string prefix) returns true or false if there exists a previously inserted word that has the prefix prefix

💡 Explanation of Solution

Trie Node (Helper Structure):
- stores children (map of characters to TrieNode pointers)
- stores a boolean `isEnd` to indicate the end of a word

Trie Class:
- insert: traverse the trie, adding characters if they dont exist
- search: check if the word exists, ensuring isEnd == true
- startsWith: check if a prefix exists, return true if found

⌛ Complexity Analysis

Constructor: O(1)
Insert: O(n) where N is the length of the word
Search: O(n) 
StartsWith: O(n)

💻 Implementation of Solution

// TrieNode represents a single character in the Trie.
class TrieNode {
public:
    unordered_map<char, TrieNode*> children; // Hash map to store child nodes (next characters in words)
    bool isEnd; // Marks if this node represents the end of a complete word
 
    TrieNode() {
        isEnd = false; // Initialize as not being the end of a word
    }
};
 
class Trie {
private:
    TrieNode* root; // Root node of the Trie
 
public:
    // Constructor initializes the root node
    Trie() {
        root = new TrieNode();
    }
 
    // Inserts a word into the Trie
    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) { // Traverse each character in the word
            // If the character does not exist, create a new TrieNode
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            // Move to the next node (child node)
            node = node->children[ch];
        }
        node->isEnd = true; // Mark the last node as the end of a word
    }
 
    // Searches for a complete word in the Trie
    bool search(string word) {
        TrieNode* node = root;
        for (char ch : word) { // Traverse each character in the word
            if (node->children.find(ch) == node->children.end()) {
                return false; // Character not found, word does not exist
            }
            node = node->children[ch]; // Move to the next node
        }
        return node->isEnd; // Return true only if it's a complete word
    }
 
    // Checks if any word in the Trie starts with the given prefix
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char ch : prefix) { // Traverse each character in the prefix
            if (node->children.find(ch) == node->children.end()) {
                return false; // Character not found, prefix does not exist
            }
            node = node->children[ch]; // Move to the next node
        }
        return true; // Prefix exists in Trie
    }
};
 
 
/**
 * 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);
 */

Graph View