23. 构建前缀树（字典树）

正文

前缀树（Trie），又称字典树，是一种多叉树结构。它通过利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

算法模板

class TrieNode {
    // 1. 26个英文字母（或其他字符集）
    val children = arrayOfNulls<TrieNode>(26)
    // 2. 标记当前节点是否为一个单词的结束
    var isEndOfWord = false
}

class Trie {
    private val root = TrieNode()

    // 向前缀树中插入一个单词
    fun insert(word: String) {
        var node = root
        for (char in word) {
            val index = char - 'a'
            if (node.children[index] == null) {
                node.children[index] = TrieNode()
            }
            node = node.children[index]!!
        }
        node.isEndOfWord = true
    }

    // 搜索前缀树中是否存在一个完整的单词
    fun search(word: String): Boolean {
        var node = findNode(word)
        return node != null && node.isEndOfWord
    }

    // 搜索前缀树中是否存在以某个前缀开头的单词
    fun startsWith(prefix: String): Boolean {
        return findNode(prefix) != null
    }

    // 私有助手函数：根据前缀找到对应的末尾节点
    private fun findNode(prefix: String): TrieNode? {
        var node = root
        for (char in prefix) {
            val index = char - 'a'
            if (node.children[index] == null) {
                return null
            }
            node = node.children[index]!!
        }
        return node
    }
}

使用说明

1. 核心特性：

   • 高效前缀匹配：查找前缀或单词的时间复杂度仅与单词长度 $L$ 相关，即 $O(L)$。
   • 空间换时间：利用数组或哈希表存储子节点，虽然空间占用较大，但查询极快。

2. 适用场景：

   • 单词搜索：如“搜索提示”、“拼写检查”。
   • 字符串排序：字典树遍历本身就是一种排序。
   • 统计词频：可以在 TrieNode 中加入 count 字段。

3. 核心技巧：

   • children 数组：如果字符集固定（如 26 个字母），使用数组速度最快；如果不固定，可改用 HashMap。
   • **isEndOfWord**：必须在插入单词的最后一个字符节点处设为 true。

4. 注意点：

   • 注意处理空字符串的特殊情况。
   • 如果需要支持删除操作，通常采用引用计数或在 isEndOfWord 置为 false 后递归删除无用节点。