zhangdizhangdi

208. 实现 Trie (前缀树) 🟨

题目

leetcode 中等

题目

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

题解

js
class Trie {
  constructor() {
    this.children = {}
  }

  insert(word) {
    let node = this.children

    console.log('➕ insert')
    console.log(`插入 ${word} 前`, JSON.stringify(this.children))

    for (const ch of word) {
      if (!node[ch]) {
        node[ch] = {}
      }
      node = node[ch]
    }
    node.isEnd = true

    console.log('插入后', JSON.stringify(this.children))
  }

  searchPrefix(prefix) {
    let node = this.children

    console.log('🔍 searchPrefix')
    console.log('搜索', prefix, JSON.stringify(node))

    for (const ch of prefix) {
      if (!node[ch]) {
        return false
      }
      node = node[ch]
    }
    return node
  }

  search(word) {
    const node = this.searchPrefix(word)
    return node !== undefined && node.isEnd !== undefined
  }

  startsWith(prefix) {
    return this.searchPrefix(prefix)
  }
}

var trie = new Trie()
trie.insert('apple')
console.log('🌰 search', trie.search('apple')) // returns true
console.log('🌰 search', trie.search('app')) // returns false
console.log('🌰 search', trie.search('le')) // returns false
console.log('🌰 startsWith', trie.startsWith('app')) // returns true
trie.insert('app')
console.log('🌰 search', trie.search('app')) // returns true
执行结果
➕ insert
插入 apple 前 {}
插入后 {"a":{"p":{"p":{"l":{"e":{"isEnd":true}}}}}}
🔍 searchPrefix
搜索 apple {"a":{"p":{"p":{"l":{"e":{"isEnd":true}}}}}}
🌰 search true
🔍 searchPrefix
搜索 app {"a":{"p":{"p":{"l":{"e":{"isEnd":true}}}}}}
🌰 search false
🔍 searchPrefix
搜索 le {"a":{"p":{"p":{"l":{"e":{"isEnd":true}}}}}}
🌰 search false
🔍 searchPrefix
搜索 app {"a":{"p":{"p":{"l":{"e":{"isEnd":true}}}}}}
🌰 startsWith { l: { e: { isEnd: true } } }
➕ insert
插入 app 前 {"a":{"p":{"p":{"l":{"e":{"isEnd":true}}}}}}
插入后 {"a":{"p":{"p":{"l":{"e":{"isEnd":true}},"isEnd":true}}}}
🔍 searchPrefix
搜索 app {"a":{"p":{"p":{"l":{"e":{"isEnd":true}},"isEnd":true}}}}
🌰 search true