Go语言中基于Trie树的高效字符串前缀匹配算法实现

Trie 比 strings.HasPrefix 遍历更高效，因其匹配时间复杂度为 O(m) 且与词典规模无关；而暴力扫描为 O(n×m)，在大规模高频匹配场景下性能显著下降。

为什么用 Trie 而不是 strings.HasPrefix

直接遍历切片调用 strings.HasPrefix 在少量字符串时够用，但当候选集超过几百条、且需高频匹配（比如路由分发、关键词过滤、自动补全），性能会明显下降。Trie 的时间复杂度是 O(m)（m 为前缀长度），与词典总大小无关；而暴力扫描是 O(n×m)（n 为词数量）。实测 10 万条路径规则下，Trie 构建后单次匹配耗时稳定在 50–200ns，暴力法则跳到 3–8μs 且波动大。

TrieNode 结构设计的关键取舍

Go 中常见错误是把 children 声明为 map[rune]*TrieNode ——这适合 Unicode 多语言场景，但绝大多数前缀匹配（如 HTTP 路由、日志关键字）只涉及 ASCII 字符，用 [128]*TrieNode 数组更省内存、更快访问。注意：数组索引必须做安全检查，rune 值超出 0–127 范围时要 fallback 到 map 或 panic。

• 若确定输入全是 ASCII（如 URL path、配置 key），用 [128]*TrieNode，访问快 3–5 倍
• 若含中文/emoji，改用 map[byte]*TrieNode（UTF-8 编码下单字节操作仍有效）或 map[rune]*TrieNode，但插入和查找变慢
• isEnd 字段不能省——它标识该节点是否对应一个完整关键词，不是所有叶子都要设 true

插入时别漏掉 isEnd 和空字符串处理

常见 bug 是插入 "a" 后，节点 a 的 isEnd = true，但插入 ""（空字符串）时没特殊处理，导致 MatchPrefix("") 返回 false。空字符串是合法前缀，应作为根节点的 isEnd 标记。

// 正确写法：显式支持空字符串
func (t *Trie) Insert(word string) {
    node := t.root
    if word == "" {
        node.isEnd = true
        return
    }
    for i := 0; i < len(word); i++ {
        b := word[i]
        if b >= 128 {
            // 处理非 ASCII 字节
            panic("unsupported byte")
        }
        if node.children[b] == nil {
            node.children[b] = &TrieNode{}
        }
        node = node.children[b]
    }
    node.isEnd = true
}

前缀匹配函数 HasPrefix 的边界逻辑

注意：Trie 的 HasPrefix 和 strings.HasPrefix 语义不同。前者只认“已插入的词中是否存在以该字符串开头的完整词”，后者是纯字符串包含判断。例如插入 "apple"，HasPrefix("app") 应返回 true（因为存在更长的匹配词），但若只插入 "app"，HasPrefix("apple") 必须返回 false（超出了已存路径）。

立即学习“go语言免费学习笔记（深入）”；

• 实现时需在遍历完输入字符串后，检查当前节点是否非 nil ——不一定要 isEnd == true，只要路径存在即可
• 如果需求是“是否存在以 s 为前缀的完整词”，才需要继续向下 DFS 查找任意 isEnd == true 的子节点
• 别在循环里提前 return false：遇到 nil 子节点才真正失败，走完所有字节后才成功

最易被忽略的是：Trie 本身不保存原始字符串，所有匹配结果都依赖结构路径。一旦插入逻辑有 off-by-one 或 isEnd 设置错位，整个前缀语义就崩了。