Trie 实现搜索自动补全与敏感词过滤

// 运行环境：Node.js 14+
// 保存为 dsa-l23.js，执行：node dsa-l23.js

class TrieNode {
  constructor() { this.children = {}; this.isEnd = false }
}
class Trie {
  constructor() { this.root = new TrieNode() }
  insert(word) {                         // 逐字符下钻，末尾标 end
    let node = this.root
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode()
      node = node.children[ch]
    }
    node.isEnd = true
  }
  startsWith(prefix) {                   // 前缀是否存在
    let node = this.root
    for (const ch of prefix) {
      if (!node.children[ch]) return false
      node = node.children[ch]
    }
    return true
  }
  collect(node, prefix, out) {           // 收集以 prefix 开头的所有词（自动补全）
    if (node.isEnd) out.push(prefix)
    for (const ch in node.children) this.collect(node.children[ch], prefix + ch, out)
  }
  autoComplete(prefix) {
    let node = this.root
    for (const ch of prefix) {
      if (!node.children[ch]) return []   // 前缀不存在
      node = node.children[ch]
    }
    const out = []
    this.collect(node, prefix, out)
    return out
  }
}

// 调用示例：搜索框补全
const t = new Trie()
;['app', 'apple', 'apply', 'apt', 'banana'].forEach(w => t.insert(w))
console.log(t.autoComplete('ap'))   // ['app','apple','apply','apt']
console.log(t.startsWith('ban'))    // true

// 敏感词过滤：遍历文本，Trie 匹配到完整词则打码
function filterSensitive(text, trie) {
  let result = '', i = 0
  while (i < text.length) {
    let node = trie.root, j = i, matched = ''
    while (j < text.length && node.children[text[j]]) {
      node = node.children[text[j]]; matched += text[j]; j++
      if (node.isEnd) break            // 命中完整敏感词
    }
    if (node.isEnd) { result += '***'; i = j } // 替换为 ***
    else { result += text[i]; i++ }
  }
  return result
}
const bad = new Trie(); ['垃圾', '广告'].forEach(w => bad.insert(w))
console.log(filterSensitive('这是垃圾信息含广告', bad)) // '这是***信息含***'