Shared 函数库

Appearance

Trie ​

前缀树（字典树）数据结构，高效的字符串检索。

函数签名 ​

typescript
function createTrie(): Trie

interface Trie {
  insert(word: string): void
  search(word: string): boolean
  startsWith(prefix: string): boolean
  autocomplete(prefix: string): string[]
  delete(word: string): boolean
  getAllWords(): string[]
  size(): number
  clear(): void
}

interface TrieNode {
  children: Map<string, TrieNode>
  isEndOfWord: boolean
  word?: string
}

API 说明 ​

insert(word: string): void ​

向 Trie 中插入一个单词。

参数：

  • word: 要插入的单词

时间复杂度：O(m)，m 为单词长度

search(word: string): boolean ​

搜索单词是否存在。

参数：

  • word: 要搜索的单词

返回值：

  • 单词存在返回 true，否则返回 false

时间复杂度：O(m)

startsWith(prefix: string): boolean ​

检查是否存在以指定前缀开头的单词。

参数：

  • prefix: 要检查的前缀

返回值：

  • 存在该前缀返回 true，否则返回 false

时间复杂度：O(m)

autocomplete(prefix: string): string[] ​

获取所有以指定前缀开头的单词（自动补全）。

参数：

  • prefix: 前缀

返回值：

  • 所有匹配的单词数组（已排序）

时间复杂度：O(m + n)，m 为前缀长度，n 为匹配单词总长度

delete(word: string): boolean ​

删除一个单词。

参数：

  • word: 要删除的单词

返回值：

  • 删除成功返回 true，单词不存在返回 false

时间复杂度：O(m)

getAllWords(): string[] ​

获取所有单词。

返回值：

  • 所有单词的数组（已排序）

时间复杂度：O(n)，n 为所有单词的总长度

size(): number ​

获取单词数量。

返回值：

  • Trie 中单词的数量

时间复杂度：O(1)

clear(): void ​

清空 Trie。

时间复杂度：O(1)

使用示例 ​

typescript
import { createTrie } from '@shared/functions/data-structures/Trie'

// 创建 Trie
const trie = createTrie()

// 插入单词
trie.insert('apple')
trie.insert('app')
trie.insert('application')
trie.insert('apply')
trie.insert('banana')

// 搜索单词
console.log(trie.search('app'))      // true
console.log(trie.search('appl'))     // false
console.log(trie.search('banana'))   // true

// 检查前缀
console.log(trie.startsWith('app'))  // true
console.log(trie.startsWith('ban'))  // true
console.log(trie.startsWith('cat'))  // false

// 自动补全
console.log(trie.autocomplete('app'))
// ['app', 'apple', 'application', 'apply']

// 获取所有单词
console.log(trie.getAllWords())
// ['app', 'apple', 'application', 'apply', 'banana']

// 删除单词
trie.delete('app')
console.log(trie.search('app'))      // false
console.log(trie.search('apple'))    // true (不影响其他单词)

// 获取单词数量
console.log(trie.size())  // 4

// 清空
trie.clear()
console.log(trie.size())  // 0

工作原理 ​

Trie（前缀树）是一种树形数据结构，用于高效地存储和检索字符串：

  1. 节点结构：

    • 每个节点包含一个字符和指向子节点的映射
    • isEndOfWord 标记该节点是否为单词结尾
    • word 存储完整单词（用于自动补全）

  2. 插入操作：

    • 从根节点开始，逐个字符向下遍历
    • 如果字符不存在，创建新节点
    • 最后标记单词结尾

  3. 搜索操作：

    • 从根节点开始，逐个字符查找
    • 检查最后节点是否标记为单词结尾

  4. 前缀匹配：

    • 只需检查路径是否存在，无需检查是否为单词结尾

空间优化：通过共享公共前缀，Trie 可以节省大量空间。

应用场景 ​

  1. 搜索引擎自动补全：输入前缀时显示建议
  2. 拼写检查：检查单词是否正确
  3. IP 路由表：最长前缀匹配
  4. 电话号码匹配：T9 输入法
  5. 字符串匹配：多模式匹配算法
  6. 词频统计：高效统计单词出现次数

经典算法 ​

搜索引擎自动补全 ​

typescript
function searchAutocomplete(trie: Trie, query: string, limit: number = 10): string[] {
  // 每次用户输入时调用
  const suggestions = trie.autocomplete(query)
  return suggestions.slice(0, limit)
}

// 使用示例
const searchTrie = createTrie()
const keywords = [
  'javascript', 'java', 'python', 'typescript',
  'react', 'vue', 'angular', 'svelte'
]
keywords.forEach(word => searchTrie.insert(word))

console.log(searchAutocomplete(searchTrie, 'ja'))
// ['java', 'javascript']

console.log(searchAutocomplete(searchTrie, 'react'))
// ['react']

拼写检查和建议 ​

typescript
function spellCheck(trie: Trie, word: string): {
  isCorrect: boolean
  suggestions: string[]
} {
  const isCorrect = trie.search(word)
  
  if (isCorrect) {
    return { isCorrect: true, suggestions: [] }
  }
  
  // 尝试去掉最后一个字符的前缀
  const prefix = word.slice(0, -1)
  const suggestions = trie.autocomplete(prefix)
  
  return { isCorrect: false, suggestions }
}

// 使用示例
const dictTrie = createTrie()
['cat', 'car', 'card', 'care', 'careful'].forEach(w => dictTrie.insert(w))

console.log(spellCheck(dictTrie, 'care'))
// { isCorrect: true, suggestions: [] }

console.log(spellCheck(dictTrie, 'carx'))
// { isCorrect: false, suggestions: ['car', 'card', 'care', 'careful'] }

单词搜索游戏（Boggle） ​

typescript
function findWords(board: string[][], dictionary: string[]): string[] {
  const trie = createTrie()
  dictionary.forEach(word => trie.insert(word))
  
  const result = new Set<string>()
  const rows = board.length
  const cols = board[0].length
  const visited = Array(rows).fill(0).map(() => Array(cols).fill(false))
  
  function dfs(row: number, col: number, path: string) {
    if (row < 0 || row >= rows || col < 0 || col >= cols || visited[row][col]) {
      return
    }
    
    path += board[row][col]
    
    if (!trie.startsWith(path)) {
      return  // 剪枝：没有以该前缀开头的单词
    }
    
    if (trie.search(path)) {
      result.add(path)
    }
    
    visited[row][col] = true
    
    // 探索 8 个方向
    for (let dr = -1; dr <= 1; dr++) {
      for (let dc = -1; dc <= 1; dc++) {
        if (dr === 0 && dc === 0) continue
        dfs(row + dr, col + dc, path)
      }
    }
    
    visited[row][col] = false
  }
  
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      dfs(i, j, '')
    }
  }
  
  return Array.from(result)
}

Trie vs 哈希表 ​

特性Trie哈希表
精确查找O(m)O(1) 平均
前缀查找O(m)不支持
自动补全O(m + n)不支持
空间效率共享前缀每个单词独立
有序遍历支持不支持

选择建议：

  • 需要前缀匹配、自动补全 → 使用 Trie
  • 只需要精确查找 → 使用哈希表
  • 数据量小 → 使用哈希表（更简单）

性能特点 ​

操作时间复杂度空间复杂度
插入O(m)O(m)
搜索O(m)-
前缀匹配O(m)-
自动补全O(m + n)O(n)
删除O(m)-

其中：

  • m = 单词/前缀长度
  • n = 匹配结果的总字符数

优化技巧 ​

  1. 压缩 Trie：合并只有一个子节点的路径
  2. 使用数组代替 Map：对于小字符集（如 26 个字母）
  3. 延迟删除：标记删除而不是物理删除
  4. 添加缓存：缓存热门前缀的查询结果

Copyright © 2023-present