算法

实现 Trie (前缀树)

loser

02 Sep 2026 • 8 min read

Trie（发音类似 "try"）或者说前缀树，是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix，返回 true；否则，返回 false。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释：

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

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数总计不超过 3 * 10^4 次

解法（数组实现的前缀树）：

class Trie {
private:
    struct TrieNode {
        bool isEnd;
        TrieNode* children[26];

        TrieNode() : isEnd(false)
        {
            for (int i = 0; i < 26; ++i)
            {
                children[i] = nullptr;
            }
        }
    };

    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* node = root;
        for (char c : word)
        {
            int idx = c - 'a';
            if (node->children[idx] == nullptr)
            {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        TrieNode* node = root;
        for (char c : word)
        {
            int idx = c - 'a';
            if (node->children[idx] == nullptr)
            {
                return false;
            }
            node = node->children[idx];
        }
        return node->isEnd;
    }

    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix)
        {
            int idx = c - 'a';
            if (node->children[idx] == nullptr)
            {
                return false;
            }
            node = node->children[idx];
        }
        return true;
    }
};

核心思想

前缀树的核心思想是：

把字符串当作一条从根节点出发的路径，路径上每个节点代表一个字符，拥有共同前缀的字符串共享同一段路径。

例如插入 "apple" 和 "app" 后，它们共享 a -> p -> p 这段路径，只有最后一个字符分叉。

这样设计的最大好处是：

存储上，公共前缀只存一份，节省空间
查询上，查找一个长度为 L 的字符串只需要走 L 步，与字符串集合的大小无关

它不像哈希表那样需要一个字符串整体作为键，而是把「按前缀检索」这件事变得非常自然。

节点结构设计

每个节点需要保存两个信息：

指向子节点的指针。因为题目保证只含小写字母，所以用固定大小 26 的数组即可：

TrieNode* children[26];

下标 0 到 25 分别对应字母 'a' 到 'z'。

一个布尔标记 isEnd，表示从根节点到当前节点的路径是否构成一个完整插入过的单词：

bool isEnd;

这个标记非常关键，它区分了「前缀」和「完整单词」。

insert 的实现

插入就是沿着字符串的每个字符，从根节点一步一步往下走：

void insert(string word) {
    TrieNode* node = root;
    for (char c : word)
    {
        int idx = c - 'a';
        if (node->children[idx] == nullptr)
        {
            node->children[idx] = new TrieNode();
        }
        node = node->children[idx];
    }
    node->isEnd = true;
}

每走到一个字符，先算出它的下标 c - 'a'。

如果对应的子节点不存在，就新建一个节点。

走到最后一个字符后，把当前节点的 isEnd 标记为 true，表示「这里是一个完整单词的结尾」。

search 的实现

查找一个完整单词，和插入的路径几乎一样：

bool search(string word) {
    TrieNode* node = root;
    for (char c : word)
    {
        int idx = c - 'a';
        if (node->children[idx] == nullptr)
        {
            return false;
        }
        node = node->children[idx];
    }
    return node->isEnd;
}

唯一的区别在最后一步：

走到 word 的最后一个字符后，必须检查这个节点的 isEnd 是否为 true。

因为路径走通只代表 word 是某个已插入单词的前缀，只有 isEnd 为 true 才代表 word 本身被插入过。

例如插入 "apple" 后，"app" 的路径能走通，但 isEnd 是 false，所以 search("app") 返回 false。

startsWith 的实现

判断前缀是否存在，路径走通即可，不需要检查 isEnd：

bool startsWith(string prefix) {
    TrieNode* node = root;
    for (char c : prefix)
    {
        int idx = c - 'a';
        if (node->children[idx] == nullptr)
        {
            return false;
        }
        node = node->children[idx];
    }
    return true;
}

只要 prefix 的每个字符都能在树上连续走到，就说明存在某个已插入单词以 prefix 开头。

search 与 startsWith 的区别

两者的遍历过程完全相同，唯一的差别在返回值：

search 要求最后一个字符节点的 isEnd == true，即 word 必须是一个完整插入过的单词
startsWith 只要求路径能走通，即 prefix 只需要是某个单词的前缀

这也是为什么 insert("apple") 后：

search("apple")   -> true   （apple 被完整插入）
search("app")     -> false  （app 只是 apple 的前缀，不是完整单词）
startsWith("app") -> true   （app 是 apple 的前缀）

边界情况

如果插入的单词是另一个单词的前缀，例如先插入 "app" 再插入 "apple"：

插入 "app" 时，在 'p' 节点标记 isEnd = true
插入 "apple" 时，继续从 'p' 节点往下建 "le"，不影响 "app" 的 isEnd
最后 search("app") 和 search("apple") 都返回 true

如果插入的单词完全相同，重复插入只是再次把 isEnd 设为 true，不会产生副作用。

如果查询的字符串比任何已插入单词都长，例如插入 "app" 后查 "apple"，走到 'e' 时发现子节点为空，直接返回 false。

正确性证明

我们证明：三个方法的行为满足题意。

结论 1：insert 正确建立单词对应的路径并标记结尾

插入时，从根节点出发，对 word 的每个字符：

若对应子节点不存在则新建
然后移动到该子节点

因此插入结束后，从根到最后一个字符节点的路径，恰好对应 word 的每个字符。

最后把该节点的 isEnd 置为 true，正确标记了单词结尾。

结论 2：search 只对完整插入过的单词返回 true

查找时，只要有一个字符对应的子节点为空，就说明 word 这条路径不存在，返回 false。

如果能走到最后一个字符，说明 word 是某个已插入单词的前缀。

此时返回 node->isEnd，只有当 word 本身被完整插入过时才为 true。

因此 search 不会把「某个单词的前缀」误判成「完整单词」。

结论 3：startsWith 能正确判断前缀是否存在

查找时，只要 prefix 的每个字符都能连续走到，就返回 true。

这说明树中确实存在一条以 prefix 结尾的路径，即存在某个已插入单词以 prefix 开头。

由于前缀不要求是完整单词，所以不需要检查 isEnd，直接返回 true。

得出结论

由结论 1 可知插入正确。

由结论 2 可知 search 正确。

由结论 3 可知 startsWith 正确。

因此 Trie 类的实现满足题意。

举例理解

以示例中的操作序列为例。

依次执行 insert("apple") 后，树的结构大致是：

root
  └─ a
      └─ p
          └─ p
              └─ l
                  └─ e  (isEnd = true)

此时：

search("apple")：路径 a -> p -> p -> l -> e 走通，且 e 节点 isEnd = true，返回 true
search("app")：路径 a -> p -> p 走通，但 p 节点 isEnd = false，返回 false
startsWith("app")：路径走通即可，返回 true

接着执行 insert("app")，在第三个 p 节点处标记 isEnd = true：

root
  └─ a
      └─ p
          └─ p  (isEnd = true)
              └─ l
                  └─ e  (isEnd = true)

此时 search("app") 返回 true。

整个过程和示例的输出一致。

复杂度分析

设 L 为当前操作的字符串长度。

insert：需要遍历 word 的每个字符，每个字符只做常数次操作。

时间复杂度：O(L)
search：最多遍历 word 的每个字符。

时间复杂度：O(L)
startsWith：最多遍历 prefix 的每个字符。

时间复杂度：O(L)

空间复杂度方面，最坏情况下，所有插入的字符串没有公共前缀，每个字符都对应一个新节点。

设所有插入单词的总长度为 N，则：

空间复杂度：O(26 * N)，也就是 O(N)

其中每个节点固定包含大小为 26 的指针数组。

这种用固定数组实现的方式，牺牲了一部分空间，换来了 O(1) 的子节点定位，是最常用的前缀树写法。