实现 Trie

GitHub跳转原题关系图返回列表

每个字符沿 next[26] 走，节点维护终点标记。

OJ: leetcodecn

题目 ID: implement-trie-prefix-tree

难度:普及+/提高

标签:Trie字典树设计cpppython

日期: 2026-07-29 13:10

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

实现 Trie（前缀树），支持 insert、search、startsWith。

思路

每个节点有 26 个子节点指针（或哈希表），isEnd 标记是否存在完整单词。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

class Trie {
    array<Trie *, 26> next = {};
    bool end = false;

public:
    Trie() {}

    void insert(string word) {
        auto cur = this;
        for (char ch : word) {
            int c = ch - 'a';
            if (!cur->next[c])
                cur->next[c] = new Trie();
            cur = cur->next[c];
        }
        cur->end = true;
    }

    bool search(string word) {
        auto cur = this;
        for (char ch : word) {
            int c = ch - 'a';
            if (!cur->next[c])
                return false;
            cur = cur->next[c];
        }
        return cur->end;
    }

    bool startsWith(string prefix) {
        auto cur = this;
        for (char ch : prefix) {
            int c = ch - 'a';
            if (!cur->next[c])
                return false;
            cur = cur->next[c];
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    Trie trie;
    while (q--) {
        string op, s;
        cin >> op >> s;
        if (op == "insert")
            trie.insert(s);
        else if (op == "search")
            cout << trie.search(s) << ' ';
        else
            cout << trie.startsWith(s) << ' ';
    }
    return 0;
}
python
#!/usr/bin/env python3
class Trie:
    def __init__(self):
        self.next = {}
        self.end = False

    def insert(self, word: str) -> None:
        cur = self
        for ch in word:
            if ch not in cur.next:
                cur.next[ch] = Trie()
            cur = cur.next[ch]
        cur.end = True

    def search(self, word: str) -> bool:
        cur = self
        for ch in word:
            if ch not in cur.next:
                return False
            cur = cur.next[ch]
        return cur.end

    def startsWith(self, prefix: str) -> bool:
        cur = self
        for ch in prefix:
            if ch not in cur.next:
                return False
            cur = cur.next[ch]
        return True


def main():
    q = int(input())
    t = Trie()
    for _ in range(q):
        op, s = input().split()
        if op == "insert":
            t.insert(s)
        elif op == "search":
            print(t.search(s), end=" ")
        else:
            print(t.startsWith(s), end=" ")


if __name__ == "__main__":
    main()

复杂度

插入/查询 O(len)，空间 O(总字符数 * 26)。

总结

Trie 用空间换时间，适合前缀匹配和词频统计。