208. 实现 Trie（前缀树）

难度：🟡 Medium | 标签：图论、Trie、设计 | 状态：⬜ LeetCode 链接

思路

每个节点存 children[26] + end 标志。 insert / search / startsWith 都是逐字符走树，区别只是终止判断。

代码

class Trie {
    struct Node {
        Node* ch[26] = {};
        bool end = false;
    };
    Node root;
public:
    void insert(string word) {
        Node* p = &root;
        for (char c : word) {
            int i = c - 'a';
            if (!p->ch[i]) p->ch[i] = new Node();
            p = p->ch[i];
        }
        p->end = true;
    }
    Node* find(const string& s) {
        Node* p = &root;
        for (char c : s) {
            int i = c - 'a';
            if (!p->ch[i]) return nullptr;
            p = p->ch[i];
        }
        return p;
    }
    bool search(string word) { auto* p = find(word); return p && p->end; }
    bool startsWith(string prefix) { return find(prefix) != nullptr; }
};

复杂度

• insert / search / startsWith 都是 O(L)
• 空间 O(总字符数 × 26)

易错 / 回顾

• search 要求完整词，所以判 end
• startsWith 只需路径存在
• 节点用 unordered_map<char, Node*> 更省空间但更慢