字典树

title: 字典树 id: 6236756795a84f489800e1e816835c77 tags: [] date: 2000/01/01 00:00:00 updated: 2023/03/04 19:29:12 isPublic: true --#|[分隔]|#--

字典树

适用场景

给定多个字符串，作为字符串集合，判断这个字符串集合中，有多少个字符串是完全重复的，拿到重复最多的那个字符串，并获得这个字符串重复的次数。

算法原理

字典树会声明一个记录对象：root，把传进来的字符串拆分成单个字母，一个个记录到root中：

• 传入 'abc'，最终的root结构如下所示

var root = {
  a: {
    b: {
      c: {
        repeatNum: 1,
      }
    }
  }
}

• 再传入 'abd'，root结构变为如下所示

var root = {
  a: {
    b: {
      c: {
        repeatNum: 1,
      },
      d: {
        repeatNum: 1,
      },
    }
  }
}

• 再分别传入 'abc'、'ab'、'ac'、he'，root最终变为如下结构：

var root = {
  a: {
    b: {
      repeatNum: 1,
      c: {
        repeatNum: 2, // 注意这里加1了
      },
      d: {
        repeatNum: 1,
      }
    },
    c: {
      repeatNum: 1,
    }
  },
  h: {
    e: {
      repeatNum: 1,
    },
  }
}

可见，root的会把每个字符串，拆分成单个字母，字母作为key添加到root中，如果某个字符是一个完整字符串的结尾，则这个字符中的repeatNum字段加1，repeatNum最终也就是这个字符串重复的次数。

root就是这些字符串的集合的字典树，字典树对象，就是维护root这个内部属性，并提供插入字符串和读取重复最多字符的方法。

代码实现

// 字典树对象
class Trie {
  constructor() {
    this.$ = Symbol('$') // 用来记录字符串重复次数
    this.root = Object.create(null) // 字典树本树
  }
  // 插入一个字符串
  insert(str) {
    let node = this.root, $ = this.$
    for (let chat of str) {
      if (!node[chat]) {
        node[chat] = {}
      }
      // 每一次循环后,node都会被赋值为字母的对象,算是递归
      node = node[chat]
    }
    if (!node[$]) node[$] = 0
    node[$]++
  }
  // 获取重复次数最多的字符串和重复次数
  most() {
    let max = 0, str = '', $ = this.$
    getMost(this.root, '')
    return { max, str }
    // 深度优先, 不停的拼接出原字符串,并拿到重复次数,和记录值 max 和 str 比较
    function getMost(obj, lastStr) {
      if (max < obj[$]) {
          max = obj[$]
          str = lastStr
        }
      for (let key in obj) {
        getMost(obj[key], lastStr + key)
      }
    }
  }
}

let trie = new Trie(), number = 100000
// 插入 number 条字符串
for (let i = 0; i < 100000; i++) {
  let str = ''
  for (let j = 0; j < 4; j++) {
    str += String.fromCharCode(Math.floor(Math.random() * 26) + 'a'.charCodeAt(0))
  }
  trie.insert(str)
}
// 获取重复数最多的字符串信息
let mostObj = trie.most()
console.log('root: ', trie.root)
console.log('单词数量: ', number)
console.log('重复最多的单词: ', mostObj.str)
console.log('重复次数: ', mostObj.max)