题面

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 104 次

分析

节点结构：
- next[ALPHABET]：存储子节点的索引，-1 表示无该子节点，避免使用指针，效率更高；
- pass：统计 “经过该节点的单词数”，是实现 countPrefix 的核心；
- end：统计 “以该节点为结尾的单词数”，是实现 search 的核心
插入逻辑：
- 从根节点（索引 0）开始，逐个字符遍历单词；
- 若字符对应的子节点不存在，创建新节点并记录索引；
- 每经过一个节点，pass 计数 + 1；
- 单词遍历结束后，结尾节点的 end 计数 + 1
查找逻辑：
- 逐个字符遍历单词，若中途子节点不存在则返回 false；
- 遍历完成后，判断结尾节点的 end 是否大于 0（是否是真实单词的结尾）
前缀统计逻辑：
- 遍历前缀到最后一个字符，返回该节点的 pass 值（所有经过该节点的单词，即以前缀开头的单词数）

代码实现

// 用class封装Trie，私有成员隐藏实现细节，公共接口提供功能
class Trie {
private:
    // 字母表大小（仅处理小写字母），私有常量
    static constexpr int ALPHABET = 26;

    // 前缀树节点结构（私有，外部不可访问）
    struct Node {
        int next[ALPHABET]; // 子节点索引（-1表示无该子节点）
        int pass;           // 经过该节点的单词数量
        int end;            // 以该节点为结尾的单词数量

        // 节点构造函数：初始化所有字段
        Node() {
            memset(next, -1, sizeof(next)); // 批量初始化next数组为-1
            pass = 0;
            end = 0;
        }
    };

    vector<Node> tree; // 存储所有节点，root固定为索引0（私有）

    // 私有辅助函数：将字符转换为0-25的索引（外部无需调用）
    inline int charToId(char c) const {
        return c - 'a'; // 仅支持小写字母，若需支持大写可额外处理
    }

public:
    // 构造函数：初始化根节点
    Trie() {
        tree.emplace_back(); // root节点（索引0）
    }

    // 公共接口1：插入单词
    void insert(const string& s) {
        int current = 0; // 从根节点开始
        tree[current].pass++; // 根节点的pass计数+1
        for (char c : s) {
            int id = charToId(c);
            // 若当前字符对应的子节点不存在，创建新节点
            if (tree[current].next[id] == -1) {
                tree[current].next[id] = tree.size(); // 新节点的索引为当前vector大小
                tree.emplace_back(); // 构造新节点
            }
            // 移动到子节点
            current = tree[current].next[id];
            tree[current].pass++; // 该节点的pass计数+1
        }
        tree[current].end++; // 单词结尾节点的end计数+1
    }

    // 公共接口2：查找单词是否存在（完全匹配）
    bool search(const string& s) const {
        int current = 0;
        for (char c : s) {
            int id = charToId(c);
            // 字符对应的子节点不存在，直接返回false
            if (tree[current].next[id] == -1) {
                return false;
            }
            current = tree[current].next[id];
        }
        // 遍历完单词后，判断是否是某个单词的结尾（end>0）
        return tree[current].end > 0;
    }

    // 公共接口3：判断是否存在以指定前缀开头的单词
    bool startsWith(const string& prefix) const {
        int current = 0;
        for (char c : prefix) {
            int id = charToId(c);
            if (tree[current].next[id] == -1) {
                return false;
            }
            current = tree[current].next[id];
        }
        // 遍历完前缀即说明存在该前缀
        return true;
    }

    // 公共接口4：统计以指定前缀开头的单词数量
    int countPrefix(const string& prefix) const {
        int current = 0;
        for (char c : prefix) {
            int id = charToId(c);
            if (tree[current].next[id] == -1) {
                return 0; // 前缀不存在，数量为0
            }
            current = tree[current].next[id];
        }
        // 返回前缀最后一个节点的pass值（即经过该节点的单词数）
        return tree[current].pass;
    }

    // 可选扩展接口：删除单词（补充常用功能）
    bool remove(const string& s) {
        // 先检查单词是否存在
        if (!search(s)) {
            return false;
        }
        int current = 0;
        tree[current].pass--;
        for (char c : s) {
            int id = charToId(c);
            int nextNode = tree[current].next[id];
            // 若子节点的pass减1后为0，可删除该子节点（优化内存）
            if (--tree[nextNode].pass == 0) {
                tree[current].next[id] = -1;
                // 注：vector无法高效删除中间节点，此处仅标记为-1，若需严格释放内存可改用其他结构
            }
            current = nextNode;
        }
        tree[current].end--;
        return true;
    }
};

实现 Trie (前缀树)

题面

分析

On this page

页面信息