208_implement_trie.cpp

/*
LeetCode 208 - Implement Trie (Prefix Tree)
Difficulty: Medium

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. 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 word is in the trie, false otherwise.
    - boolean startsWith(String prefix) Returns true if there is a previously inserted string
      that has the prefix prefix, and false otherwise.

Example 1:
    Input: ["Trie","insert","search","search","startsWith","insert","search"]
           [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
    Output: [null,null,true,false,true,null,true]

Time Complexity: O(m) for all operations, where m is key length
Space Complexity: O(m) for insert, O(1) for search/startsWith
*/

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

using namespace std;

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

    TrieNode() : is_end(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->is_end = 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->is_end;
    }

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

int main() {
    Trie trie;
    trie.insert("apple");
    cout << (trie.search("apple") ? "true" : "false") << endl;     // true
    cout << (trie.search("app") ? "true" : "false") << endl;       // false
    cout << (trie.startsWith("app") ? "true" : "false") << endl;   // true
    trie.insert("app");
    cout << (trie.search("app") ? "true" : "false") << endl;       // true

    return 0;
}