实现 Trie：字母当路标，前缀共用
每个节点是一个字符，根到某节点的路径拼出一个前缀。插入沿路走、缺了就建；search 与 startsWith 的差别，只在最后那一眼 isEnd。
节点结构 TrieNode{ children: [26]*TrieNode; isEnd bool }。插入与查询都从根出发逐字符行走：孩子存在则下移，不存在则新建（插入）或判定缺失（查询）。search 要求走到终点且 isEnd=true；startsWith 只要求路径存在。时间 O(len)，空间 O(总字符数)。
实现一个前缀树（Trie），支持 insert(word)、search(word)、startsWith(prefix) 三种操作。
为什么需要它？把单词逐字符展开成共享路径，公共前缀只存一份——比哈希集合省空间，还能高效回答「有哪些单词以某前缀开头」。
这道题真正的考点不是代码量，而是理解一个边界：路径存在 ≠ 单词存在。'app' 可以是 'apple' 的前缀，但只有当有人真正 insert 过 'app'，它才算一个单词。isEnd 就是用来记录这一点的。
把单词翻译成路径
想象一座档案馆：中央是入口大厅（根节点），从大厅出发，每一个字母都是一条通往下一层的通道。
插入单词 'apple'，就是在大厅里找到 'a' 的通道、走进去，再找 'p' 的通道、走进去……直到 'e' 为止。每个走过的房间就是一个节点，代表「从根到这里拼出的前缀」。
用代码表达：节点不存整个单词，只存 26 个孩子槽位（对应 a–z）和一个 isEnd 布尔标记。整个单词的信息分散在从根到该节点的路径上。
所以「节点」真正代表的是一段前缀，而不是一个单词——这是理解后面一切的基础。
路径即单词根到某节点的每一条边是一个字母，连起来就是这段前缀；isEnd 只在路径尽头是一个完整单词时点亮。
插入：沿路走，缺了就建
insert 的规则只有两条：从根出发逐字符走，孩子存在就下移，不存在就新建并下移；走到最后一个字符的房间，点亮 isEnd。
先插 'apple'：a、p、p、l、e 全都要新建，最后给 'e' 房间点亮 isEnd。
再插 'app'：前三个字符 a、p、p 的路已经存在（刚才建的），直接复用，不需要新建；走到第三个 'p' 房间，点亮它的 isEnd。
注意这里发生了什么：'app' 与 'apple' 共享了 a→p→p 三个房间，只在第 4 层分岔（一个去 l、一个在此结束）。共享前缀 = 共享节点，这正是 Trie 省空间的来源。
共享先插 apple 再插 app：app 不用新建任何节点，只要点亮第三个 p 的 isEnd 即可。
search：路径存在，且尽头是单词
search(word) 要做两件事：一是沿着字符走，全程路径都必须存在（任意一步发现孩子为空，立即返回 false）；二是走到终点时，检查这个房间的 isEnd 是否为 true。
为什么第二步必不可少？因为路径存在只说明「这个前缀出现过」，不代表「这个词被完整插入过」。
例：只 insert 过 'apple'。search('app') 路径存在（a→p→p），但第三个 p 的 isEnd 为 false（它只是 apple 的中间节点）——返回 false。而 search('apple') 路径存在且 e 的 isEnd 为 true——返回 true。
这就是 isEnd 的全部意义：把「曾经作为前缀被走过」和「被完整插入为单词」区分开。
边界search 比 startsWith 多一个 isEnd 检查。它决定了 'app' 在只有 'apple' 被插入时返回 false。
startsWith：只看路径
startsWith(prefix) 是 search 的放宽版：只要能从根走到 prefix 的最后一个字符，就返回 true——完全不检查 isEnd。
因为「是否存在以某前缀开头的单词」只关心前缀路径本身是否存在，不关心这个前缀是不是一个完整单词。
插过 'apple' 后：startsWith('app') → true（即使 'app' 不是单词）；startsWith('apx') → false（走到 x 时发现孩子为空，路径断了）。
这刚好和 search 形成对照：search 严格（要 isEnd），startsWith 宽松（只要路径）。两个操作合起来，就是 Trie 对外提供的全部能力。
易错点与复杂度
第一个坑：忘掉 isEnd 检查。只比路径会导致 search('app') 在只插过 'apple' 时错误返回 true。
第二个坑：重复插入同一单词。insert 走既有路径、再次点亮 isEnd，无害但要注意幂等。
第三个坑：用 map[rune]*TrieNode 替代 [26] 数组。功能等价，但用固定数组能免去哈希开销，且便于讨论空间。
复杂度：时间 O(len)——insert/search/startsWith 都是遍历一次单词长度。空间 O(总字符数)——每个字符贡献一个节点，节点数等于所有插入单词的字符总数（去重后）。
LC211 把 '.' 通配符引入 search，需要在匹配到 '.' 时遍历全部孩子；LC648 用 Trie 做单词替换。掌握这道题的结构，那些都是小改。
面试表达先画一条 apple 的路径，再解释 app 复用前三层、点亮 isEnd——两个操作和一个边界就讲完了。
Go：Trie 结构
type Trie struct {children [26]*TrieisEnd bool}func Constructor() Trie { return Trie{} }func (t *Trie) Insert(word string) {n := tfor _, ch := range word {idx := ch - 'a'if n.children[idx] == nil {n.children[idx] = &Trie{}}n = n.children[idx]}n.isEnd = true}func (t *Trie) Search(word string) bool {n := tfor _, ch := range word {idx := ch - 'a'if n.children[idx] == nil { return false }n = n.children[idx]}return n.isEnd}func (t *Trie) StartsWith(prefix string) bool {n := tfor _, ch := range prefix {idx := ch - 'a'if n.children[idx] == nil { return false }n = n.children[idx]}return true}
1节点：26 个孩子槽 + 词尾标记。
2从根出发。
3槽位为空则新建。
4下移一个节点。
5词尾打标记。
6Search 沿路径走。
7任何一步孩子为空即返回 false。
8终点必须 isEnd=true。
9StartsWith 同样沿路径走。
10只要路径存在就返回 true，不检查 isEnd。
总结
Trie = 字符路径 + isEnd 词尾标记；insert 建路，search 验标，startsWith 只看路。
- 每个节点是一个前缀，路径拼出单词；公共前缀共享节点。
- isEnd 区分「完整单词」与「只是前缀」，是 search 的边界。
- insert 缺了建路、search 断路返回 false、startsWith 不查 isEnd。
- 时间 O(len)，空间 O(总字符数)；LC211 用 '.' 通配符需遍历孩子。