直接回答

字典树（前缀树）是一种多叉树，每条边代表一个字符，从根到某节点的路径拼出一个前缀，节点上标记是否为完整单词。插入和查询的时间都是 O(L)（L 为串长），与词典规模无关，并且天然支持前缀查询。

展开解析

核心优势是把"按前缀"检索从 O(词典大小×串长) 降到 O(串长)，且共享前缀节省空间。节点结构：子节点指针数组（小字符集如 26 个字母）或哈希表（大字符集省空间），外加 isEnd 标志。应用：搜索自动补全/输入提示、拼写检查、IP 路由最长前缀匹配、字符串排序、异或最大对等位运算问题（二进制 Trie）。局限：节点指针开销大，内存占用高，可用双数组 Trie、压缩路径的 Radix Tree 优化。易错点：查找单词要同时满足路径存在且 isEnd 为真，前缀查询则只要求路径存在。追问方向：实现 startsWith 与 search、通配符匹配（. 时遍历所有孩子 DFS）、与哈希表的取舍——哈希表查单词也是 O(L) 但不支持前缀枚举和字典序遍历。