字典树

字典树介绍

实现

class TrieNode {
  count = 0
  children: Map<string, TrieNode> = new Map()
}

class Trie {
  root = new TrieNode()

  insert(word: string): void {
    let cur = this.root
    for (let j = 0; j < word.length; j++) {
      const char = word[j]
      if (!cur.children.has(char)) {
        cur.children.set(char, new TrieNode())
      }
      cur = cur.children.get(char)
    }
    cur.count++
  }

  build(words: string[]): void {
    for (let i = 0; i < words.length; i++) {
      this.insert(words[i])
    }
  }

  find(word: string): number {
    let cur = this.root
    for (let i = 0; i < word.length; i++) {
      const char = word[i]
      if (!cur.children.has(char)) {
        return 0
      }
      cur = cur.children.get(char)
    }
    return cur.count
  }
}

测试

const tree = new Trie()
tree.build(['hello', 'hello'])
console.log(tree.find('hello')) // 2
console.log(tree.find('world')) // 0
tree.insert('world')
console.log(tree.find('world')) // 1