跳到主要内容

LeetCode 208. 实现 Trie（前缀树）

本节目标

用路径与终止标记区分前缀存在和完整单词存在。

这道题实现匹配与字典树中的前缀结构：支持插入单词、查询完整单词，以及查询某个前缀是否存在。

查看 LeetCode 原题

题意与约束​

设计 Trie，提供 insert(word)、search(word) 和 startsWith(prefix)。插入 apple 后，search("apple") 为真，startsWith("app") 也为真，但 search("app") 仍为假；只有再插入 app，完整查询才变为真。

朴素思路与瓶颈​

把所有单词存入数组或集合，完整查询可以较快完成，但前缀查询需要逐个判断候选词。若许多单词共享开头，像 apple、app、apply，重复保存和比较 app 也会浪费工作。

路径与完整单词的边界​

Trie 从根开始，每条边代表一个字符。根到一个节点的路径表示某个前缀；例如插入 apple 后，a → p → p 的路径已经存在，因此 startsWith("app") 为真。

但路径存在并不等于完整单词存在。每个节点额外维护终止标记 isWord：apple 末尾节点为真，app 节点在只插入 apple 时为假。search 必须同时检查路径和终止标记，startsWith 只检查路径。

代码实现​

C++ 使用节点数组和 26 个小写字母子边；缺失子边记为 -1。Python 使用字符到子节点的映射。两种实现都没有独立入口，直接保留题目要求的 Trie、insert、search、startsWith 接口。

C++17
#include <array>
#include <string>
#include <vector>

using namespace std;

class Trie {
private:
    struct Node {
        array<int, 26> children{};
        bool isWord = false;

        Node() {
            children.fill(-1);
        }
    };

    vector<Node> nodes;

public:
    Trie() {
        nodes.emplace_back();
    }

    void insert(string word) {
        int node = 0;
        for (char ch : word) {
            const int child = ch - 'a';
            if (nodes[node].children[child] == -1) {
                nodes[node].children[child] = static_cast<int>(nodes.size());
                nodes.emplace_back();
            }
            node = nodes[node].children[child];
        }
        nodes[node].isWord = true;
    }

    bool search(string word) {
        const int node = findNode(word);
        return node != -1 && nodes[node].isWord;
    }

    bool startsWith(string prefix) {
        return findNode(prefix) != -1;
    }

private:
    int findNode(const string& value) const {
        int node = 0;
        for (char ch : value) {
            const int child = ch - 'a';
            if (nodes[node].children[child] == -1) {
                return -1;
            }
            node = nodes[node].children[child];
        }
        return node;
    }
};

复杂度分析​

  • 插入长度为 L 的单词需要 O(L) 时间。
  • search 与 startsWith 都只沿一条路径前进，时间复杂度为 O(L)。
  • 空间复杂度与所有不同前缀节点数成正比。

易错点​

  • 用“能走到节点”作为 search 的成功条件，误把前缀当成单词。
  • 插入时没有为新字符创建节点，或覆盖已经存在的共享路径。
  • 让 startsWith 检查终止标记，导致合法但未单独插入的前缀被错误拒绝。
  • 在 LeetCode 类题中加入读取输入、输出或 main，破坏平台接口。

模式迁移​

Trie 可以扩展为统计经过节点的单词数、按字典序枚举、记录词频，或在二进制位上构成异或字典树。无论节点保存什么附加信息，路径存在与完整单词结束仍是最基本、不能混淆的两层语义。