这道题的要求可以分为两个部分：
- 首先根据输入的所有字符串和频率我们需要能够记录下来，然后在user输入每一个新字符的时候，我们要找到所有以这个prefix开头的字符串然后返回按照出现频率从高到低的前三个热词
- 之后对于每一个user新输入的词(以#结尾)，我们也需要动态地更新我们已有的数据
解决这个问题的思路就是用Trie，对于每一个节点，我们存所有以这个prefix开头的词。每次查询的时候，我们找到对应的节点，然后返回出现频率的前三个即可，之后在插入完整的词到trie当中更新即可。假设初始输入n个词，平均长度为m，查询字符串的长度为k，那么初始化的时间复杂度为O(m * n)，查询的时间复杂度为O(k)。空间复杂度的话，因为每一次会在其经过的所有节点上存一份，也就是m份，每一份长度为m，而总共有n个这样的词，所以总的空间复杂度为O(n * m^2)。代码如下：
No comments:
Post a Comment