关于Trie树的一个面试题


设计一个算法可以自动列出以输入字符串为前缀的单词中最频繁查找的前10个单词。
注:类似google搜索框中输入要查找的单词,输入前缀google会自动列出同一前缀的所有查找单词中top 10的
已邀请:

赞同来自: x4168138


1、 节点上记录每个单词被查找的次数
2、 对于给定的输入词,找到其在Trie中的位置,设为节点K
3、 搜索以节点K为根的子树,用一个最小堆记录top10
这里需要注意的一个地方是,给定的输入词可能是一个词,也可能不是一个词,如果是一个词,这个词也要放入到最小堆中

要回复问题请先登录注册