題目：
實作一個 Trie（前綴樹），也稱為字典樹，來支持以下兩種操作：

• insert(word)：插入字串 word 到 Trie 中。
• search(word)：回傳 word 是否在 Trie 中。
• startsWith(prefix)：回傳是否有任何字串在 Trie 中以給定的 prefix 為前綴。

範例：

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 回傳 true
trie.search("app");     // 回傳 false
trie.startsWith("app"); // 回傳 true
trie.insert("app");   
trie.search("app");     // 回傳 true

解題思路

children 表示該節點的子節點，用來儲存下個字元的節點。
isEnd 是用來標記這個節點是否是某個單詞的結尾。

實作：

class Trie {
private:
    struct TrieNode {
        unordered_map<int, TrieNode*> children; // 子節點
        bool isEnd = false; // 是否為一個單詞的結尾
        
        TrieNode() {}
    };

    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* node = root;
        for (auto c : word) {
            // 檢查有沒有存在，沒存在則建立
            if (!node->children.count(c)) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        TrieNode* node = root;
        for (auto c : word) {
            // 檢查有沒有存在，沒存在則 return false
            if (!node->children.count(c)) {
                return false;
            }
            node = node->children[c];
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (auto c : prefix) {
            // 檢查有沒有存在，沒存在則 return false
            if (!node->children.count(c)) {
                return false;
            }
            node = node->children[c];
        }
        return true;
    }
};

參考：
#208. Implement Trie (Prefix Tree)