如何实现一个字典树（Trie）？插入、查找、前缀匹配怎么写？

简化版

一个 Trie 节点存两样东西：children（子节点，26 个字母用数组或用哈希表）和 isEnd（是否是单词结尾）。插入：沿字符逐个走，没有子节点就新建，最后一个字符的节点标 isEnd=true。查找单词：沿字符走，走不通返回 false，走通后看最后节点的 isEnd。前缀匹配 startsWith：沿字符走通即可，不看 isEnd。三者都是 O(L)。

详细版

class Trie {
    private final Trie[] children = new Trie[26]; // 小写字母
    private boolean isEnd = false;

    public void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new Trie(); // 没有就新建
            node = node.children[i];
        }
        node.isEnd = true;                 // 标记单词结尾
    }

    public boolean search(String word) {   // 查完整单词
        Trie node = find(word);
        return node != null && node.isEnd; // 必须走通 且 是单词结尾
    }

    public boolean startsWith(String prefix) { // 查前缀
        return find(prefix) != null;       // 走通即可，不看 isEnd
    }

    private Trie find(String s) {           // 沿字符下降，返回终点节点或 null
        Trie node = this;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) return null; // 走不通
            node = node.children[i];
        }
        return node;
    }
}

search 和 startsWith 的唯一区别：前者要求终点 isEnd=true（是完整单词），后者只要能走通（是前缀就行）。

完整版教学

一、节点设计：children + isEnd

一个 Trie 节点只需两个字段：

children：指向子节点。小写字母用长度 26 的数组，children[c-'a'] 直接定位；字符集大就用 Map<Character, TrieNode>。
isEnd：布尔标记，表示「从根到当前节点的路径是否构成一个被收录的完整单词」。

注意：Trie 节点本身不需要存字符——字符信息藏在「父节点用哪个下标/键指向它」里。这也是「路径表示字符串」思想的体现。

二、插入：走不通就建路

插入单词就是沿着字符一个个往下走，把路「铺」出来：

从根开始，取当前字符对应的子节点。
如果子节点不存在，新建一个。
移动到子节点，处理下一个字符。
所有字符处理完，把最后一个节点的 isEnd 置 true。

如果插入的单词和已有单词有公共前缀，前半段路径会被复用，只有分叉后的部分才新建节点——这就是公共前缀共享。

三、查找单词：走通 + isEnd

查一个完整单词分两步判断，缺一不可：

能不能沿字符走通：任何一步找不到对应子节点，说明这条路径不存在，返回 false。
终点是不是 isEnd：即使走通了，还要看终点 isEnd 是否为 true。因为路径存在只说明它是「某个词的前缀」，不代表它本身是被收录的完整单词。

比如只插了 apple，查 app 时路径能走通，但 app 那个节点 isEnd=false，所以 search("app") 应返回 false。

四、前缀匹配：只要走通

startsWith(prefix) 判断「有没有单词以 prefix 开头」，只需要能沿字符走通即可，不关心 isEnd。因为只要这条前缀路径存在，就一定有单词经过它（否则这些节点不会被创建）。这正是 search 和 startsWith 的唯一区别——一个看 isEnd，一个不看。

五、复杂度

插入 / 查找 / 前缀匹配：都是 O(L)，L 为操作字符串的长度，与 Trie 里已有多少单词无关。
空间：最坏 O(单词总字符数 × 字符集大小)，节点较多（见复杂度专题）。

六、常见误区与追问

考点	正确口径
insert	走不到的边就创建节点，末尾设 `isEnd`
search	路径走通且末尾 `isEnd=true`
startsWith	路径走通即可，不要求 `isEnd`

class Node:
  children
  isEnd
Trie:
  root = new Node()

实现 Trie 时，search 和 startsWith 最大区别就在最后是否检查 isEnd。

误区：前缀存在就说明单词存在。 app 存在不代表 apple 存在，反过来也不代表 app 是完整词，必须看 isEnd。
误区：插入时每个字符都必须新建节点。 已有路径要复用，只在缺少孩子时创建新节点。
误区：root 代表第一个字符。 root 通常是空前缀，不存实际字符，从它的 children 开始走。
追问：如何支持任意字符集？ 用 Map 存 children，比固定数组更灵活，但常数开销更大。
追问：如何统计前缀出现次数？ 可在节点上维护 pass/count，插入经过时累加，删除时递减。
追问：复杂度是多少？ 插入、查找、前缀匹配都是 O(L)，空间与新增节点数有关。

七、加强记忆

Trie 节点 = children（数组或哈希表）+ isEnd，节点本身不存字符（字符藏在指向它的下标里）。插入沿字符走、缺则新建、末节点 isEnd=true；search 要「走通且终点 isEnd=true」；startsWith 只要「走通」（不看 isEnd）——这是两者唯一区别（app 是 apple 前缀但 search 应返回 false）。三个操作都 O(L)，与单词数量无关。

简化版

详细版