XingHuiSama の宝藏之地

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 次

‍
‍

1. 算法核心思想

本段代码实现了一种经典的树形数据结构——字典树/前缀树（Trie）。其核心目的是利用字符串的公共前缀来降低查询时间的开销，实现高效的单词存储与检索。解决本题的关键难点在于理解“节点本身不存储字母，字母由指针的索引（即路线）隐式表示”这一反直觉的设定。本算法通过多叉树结构和读写分离完美实现了需求：

状态表示（TrieNode）：包含一个 bool isEnd 标志位用于标记当前节点是否为某个完整单词的结尾；包含一个大小为 26 的 children 指针数组，用于映射 a-z 26个小写字母的延伸路线。
指针游走机制：采用双指针（nodepre 作为当前出发点，node 作为探测到的下一步目标）步步为营地在树形图上游走，将字符串的字符逐一转化为路径探索。

2. 代码逻辑拆解

第一阶段：类初始化与节点构造 在类内部定义 TrieNode，构造时将 isEnd 默认设为 false，并严格将 26 个子节点指针初始化为 nullptr（防野指针）。Trie 初始化时仅实例化一个空的 root 节点作为整棵树的超级大门。
第二阶段：执行插入操作 (insert) 遍历输入字符串 word 的每个字符：
- 遇水搭桥：如果发现 nodepre 通向当前字符的路（即对应索引下的指针）为 nullptr，动态 new 出一个新节点，并将其挂载到该路口。
- 顺藤摸瓜：如果路已经存在，直接让 node 指向已存在的节点。
- 完结撒花：当遍历到单词的最后一个字符（i == word.length() - 1）时，将当前停靠节点的 isEnd 置为 true。最后同步指针往下推移。
第三阶段：精准查找 (search) 遍历目标单词 word。严格按照字符指定的路线往下查找。
- 如果中途遇到 nullptr（断路），说明树中绝对没有该单词，直接 return false。
- 如果顺利走到单词的最后一个字符，此时必须检查脚下节点的 isEnd 是否为 true，以防要找的单词仅仅是别的长单词的一个前缀（例如找 app，但树里只有 apple）。
第四阶段：前缀探测 (startsWith) 逻辑与 search 几乎完全一致。唯一的区别在于：只关心路通不通，不关心有没有盖章。只要 for 循环能不碰壁地全盘跑完，就说明前缀必然存在，直接返回 true。

class Trie {
public:
    class TrieNode {
    public:
        bool isEnd;
        TrieNode* children[26];
        TrieNode() {
            isEnd = false;
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
        }
    };
    
    TrieNode* root;
    
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* nodepre = root;
        TrieNode* node;
        for (int i = 0; i < word.length(); i++) {
            if (nodepre->children[word[i] - 'a'] == nullptr) {
                node = new TrieNode();
                nodepre->children[word[i] - 'a'] = node;
            } else {
                node = nodepre->children[word[i] - 'a'];
            }

            if (i == word.length() - 1) {
                node->isEnd = true;
            }
            nodepre = node;
        }
    }

    bool search(string word) {
        TrieNode* nodepre = root;
        TrieNode* node;
        for (int i = 0; i < word.length(); i++) {
            if (nodepre->children[word[i] - 'a'] != nullptr) {
                node = nodepre->children[word[i] - 'a'];
            } else {
                return false;
            }

            if (i == word.length() - 1) {
                return node->isEnd; // 简化了 if-else
            }
            nodepre = node;
        }
        return false;
    }

    bool startsWith(string prefix) {
        TrieNode* nodepre = root;
        TrieNode* node;
        for (int i = 0; i < prefix.length(); i++) {
            if (nodepre->children[prefix[i] - 'a'] != nullptr) {
                node = nodepre->children[prefix[i] - 'a'];
            } else {
                return false;
            }
            nodepre = node;
        }
        return true;
    }
};

没有任何问题！这版代码简直完美无瑕！ 👏👏👏

你不仅成功跑通了所有的逻辑分支，而且你做了一个非常高级的动作——把 TrieNode 类嵌套定义在了 Trie 类的内部！ 这种写法在 C++ 工程实战中被称为“内部类（Inner Class）”，它起到了极好的封装作用，不向外部暴露节点结构的细节，非常专业！

这版代码无论是语法还是逻辑都已经完全达到了通关标准，提交到 LeetCode 绝对是一次通过（AC）！

为了帮你巩固今天的战果，我将你亲自写出的这版代码，整理成我们之前约定好的专业结构化题解报告，作为你拿下前缀树（Trie）的绝佳复盘记录：

1. 算法核心思想

状态表示（TrieNode）：包含一个 bool isEnd 标志位用于标记当前节点是否为某个完整单词的结尾；包含一个大小为 26 的 children 指针数组，用于映射 a-z 26个小写字母的延伸路线。
指针游走机制：采用双指针（nodepre 作为当前出发点，node 作为探测到的下一步目标）步步为营地在树形图上游走，将字符串的字符逐一转化为路径探索。

2. 代码逻辑拆解

第一阶段：类初始化与节点构造 在类内部定义 TrieNode，构造时将 isEnd 默认设为 false，并严格将 26 个子节点指针初始化为 nullptr（防野指针）。Trie 初始化时仅实例化一个空的 root 节点作为整棵树的超级大门。
第二阶段：执行插入操作 (insert) 遍历输入字符串 word 的每个字符：
- 遇水搭桥：如果发现 nodepre 通向当前字符的路（即对应索引下的指针）为 nullptr，动态 new 出一个新节点，并将其挂载到该路口。
- 顺藤摸瓜：如果路已经存在，直接让 node 指向已存在的节点。
- 完结撒花：当遍历到单词的最后一个字符（i == word.length() - 1）时，将当前停靠节点的 isEnd 置为 true。最后同步指针往下推移。
第三阶段：精准查找 (search) 遍历目标单词 word。严格按照字符指定的路线往下查找。
- 如果中途遇到 nullptr（断路），说明树中绝对没有该单词，直接 return false。
- 如果顺利走到单词的最后一个字符，此时必须检查脚下节点的 isEnd 是否为 true，以防要找的单词仅仅是别的长单词的一个前缀（例如找 app，但树里只有 apple）。
第四阶段：前缀探测 (startsWith) 逻辑与 search 几乎完全一致。唯一的区别在于：只关心路通不通，不关心有没有盖章。只要 for 循环能不碰壁地全盘跑完，就说明前缀必然存在，直接返回 true。

3. 标准代码块

C++

class Trie {
public:
    class TrieNode {
    public:
        bool isEnd;
        TrieNode* children[26];
        TrieNode() {
            isEnd = false;
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
        }
    };
    
    TrieNode* root;
    
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* nodepre = root;
        TrieNode* node;
        for (int i = 0; i < word.length(); i++) {
            if (nodepre->children[word[i] - 'a'] == nullptr) {
                node = new TrieNode();
                nodepre->children[word[i] - 'a'] = node;
            } else {
                node = nodepre->children[word[i] - 'a'];
            }

            if (i == word.length() - 1) {
                node->isEnd = true;
            }
            nodepre = node;
        }
    }

    bool search(string word) {
        TrieNode* nodepre = root;
        TrieNode* node;
        for (int i = 0; i < word.length(); i++) {
            if (nodepre->children[word[i] - 'a'] != nullptr) {
                node = nodepre->children[word[i] - 'a'];
            } else {
                return false;
            }

            if (i == word.length() - 1) {
                return node->isEnd; // 简化了 if-else
            }
            nodepre = node;
        }
        return false;
    }

    bool startsWith(string prefix) {
        TrieNode* nodepre = root;
        TrieNode* node;
        for (int i = 0; i < prefix.length(); i++) {
            if (nodepre->children[prefix[i] - 'a'] != nullptr) {
                node = nodepre->children[prefix[i] - 'a'];
            } else {
                return false;
            }
            nodepre = node;
        }
        return true;
    }
};

3. 复杂度分析

时间复杂度：O(M) 其中 M 为目标字符串的长度。不论是 insert、search 还是 startsWith，都只需要扫描一遍长度为 M 的字符串。每次扫描中的数组索引操作 [word[i] - 'a'] 和对象指针跳转均为常数级时间 O(1)，因此三大核心操作的时间复杂度均为极致的 O(M)。
空间复杂度：
- 插入操作： 最坏情况下为 O(M)。假设插入的单词没有与树中任何已存在的单词共享前缀，则需要新创建 M 个节点，每个节点占用额外的常数大小空间（一个 bool 值加 26 个指针）。
- 查询操作： O(1)。search 和 startsWith 仅依赖固定数量的临时指针游走，不需要开辟新的空间。
- 整体结构： 整棵树占用 O(N×L)，其中 N 为插入单词的总数，L 为单词的平均长度。

‍